这道题目一点也不卡素数的判断
就是朴素的sqrt(n) 也不卡
所以~放心的用吧。
构造回文的时候看了HINT
其中是这么写的:
Generate palindromes by combining digits properly. You might need more than one of the loops like below. /* generate five digit palindrome: */
for (d1 = 1; d1 <= 9; d1+=2) { /* only odd; evens aren't so prime */
for (d2 = 0; d2 <= 9; d2++) {
for (d3 = 0; d3 <= 9; d3++) {
palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;
... deal with palindrome ...
}
}
}
Source Code:
/*
ID: wushuai2
PROG: pprime
LANG: C++
*/
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int M = ;
const ll P = 10000000097ll ;
const int INF = 0x3f3f3f3f ;
const int MAX_N = ;
const int MAXSIZE = ; bool primei(int n){
int i, j;
for(i = ; i <= sqrt(n); ++i){
if(n % i == ) return false;
}
return true;
} ll b[]={,,};
int p[]={,,,,,,,};
bool prime(int n){
int i = , j, q;
if(n == ) return false;
if(n == || n == || n == ) return true;
if(n % == || n % == || n % == ) return false;
q = (int)sqrt((double)n);
for(; i <= q; ){
for(j = ; j < ; ++j){
if(n % i == ) return false;
i += p[j];
}
if(n % i == ) return false;
}
return true;
}
int creat(){
int i, j, k, l, m, count = ;
for(i = ; i <= ; i += )
for(j = ; j <= ; ++j)
b[count++] = * i + * j + i;
for(i = ; i <= ; i += )
for(j = ; j <= ; ++j)
for(k = ; k <= ; ++k)
b[count++] = * i + * j + k * + j * + i;
for(i = ; i <= ; i += )
for(j = ; j <= ; ++j)
for(k = ; k <= ; ++k)
for(l = ; l <= ; ++l)
b[count++] = * i + * j + k * + l * + k * + j * + i;
return count - ;
} int main() {
ofstream fout ("pprime.out");
ifstream fin ("pprime.in");
int i, j, k, t, n, s, c, w, q;
int a;
n = creat();
fin >> a >> c;
for(i = ; i < n; ++i){
if(b[i] >= a){
if(b[i] > c) break;
if(prime(b[i])){
fout << b[i] << endl;
}
}
} fin.close();
fout.close();
return ;
}