上学期作业题，但是当时打表近乎作弊，正好在洛谷上又遇到了，重做温习。
方法一：先利用筛法求出1~b的所有素数，存入到Prime数组中，再逐一判断是否为回文数
可是如果范围是1~100000000，则共有5761456个素数；
代码如下：
#include<iostream>
#include<fstream>
#include<cstring>
#include<ctime>
using namespace std;
const int N=1E8; //注意：1E8是浮点数，进行了强制类型转换
bool isPrime[N]={};
int Prime[6*1000000];
bool ifPalindrome(int n){
int s[8]={};
int cnt=0;
while(n>0){
s[cnt++]=n%10;
n=n/10;
}
for(int i=0;i<cnt/2;i++){
if(s[i]!=s[cnt-1-i]){
return false;
}
}
return true;
}
int main(){
ofstream fout;
fout.open("prime.txt");
int a,b;
cin >> a >> b;
time_t begin,end;
begin=clock();
int cnt=0;
for (int i = 2; i <= b; i++)
isPrime[i] = true;
for (int i = 2; i * i <= b; i++)
if (isPrime[i])
for (int j = i * i; j <= b; j += i)
isPrime[j] = false;
for (int i = 2; i <= b; i++)
if (isPrime[i]){
Prime[cnt++]=i;
}
for(int i=0;i<cnt;i++){
if(Prime[i]>=a)
if(ifPalindrome(Prime[i])){
fout << Prime[i] << endl;
}
}
end=clock();
fout<<"runtime: "<<double(end-begin)<<endl;
fout.close();
return 0;
}
///CLOCKS_PER_SEC
但是交上去以后发现第十个点总是TLE，遂通过<ctime>头文件获得当前时间从而相减获得程序运行时间（注意:此时间包括屏幕输出的时间，且单位为ms；可以除以1000（即常数CLOCKS_PER_SEC）以s为单位）
发现无论如何优化，该算法的特性限制了没有办法在1000ms内完成，一旦b的值较大（比如就是10^8时）无论abs(b-a)大小，所花时间都是2000+ms，因为此时筛法确实需要这么长的时间；
除去打表，也只能改变策略，不要先求1~b的全部素数再求回文数，而要先获得a~b的全部回文奇数（且个位非5）再判断是否为素数
方法二：先获得a~b的全部回文奇数，再判断是否为素数
1. 先求出100~100000000的全部回文奇数再找a~b范围内的？
2. 直接求出a~b之间的回文奇数？
3. 折中——求a,b的位数，找到该范围内的回文奇数 100~100000000之内的回文奇数总共才只有11100个
4. 判断是否为素数用什么方式？就用最原始的方式，每次判断的复杂度是O(n)
下面是AC代码：
#include<iostream>
#include<cstring>
#include<ctime>
#include<fstream>
using namespace std;
int palindrome[20000]={}; //100~100000000共有11100个回文奇数；
int cnt=0;
int digit(int n){
int index=0;
while(n>0){
n=n/10;
index++;
}
return index;
}
void create(int n){
int d1,d2,d3,d4;
switch(n){
case 3:
for(d1=1;d1<=9;d1+=2)
for(d2=0;d2<=9;d2++)
palindrome[cnt++]=d1*100+d2*10+d1;
break;
case 4:
for(d1=1;d1<=9;d1+=2)
for(d2=0;d2<=9;d2++)
palindrome[cnt++]=d1*1000+d2*100+d2*10+d1;
break;
case 5:
for(d1=1;d1<=9;d1+=2)
for(d2=0;d2<=9;d2++)
for(d3=0;d3<=9;d3++)
palindrome[cnt++]=d1*10000+d2*1000+d3*100+d2*10+d1;
break;
case 6:
for(d1=1;d1<=9;d1+=2)
for(d2=0;d2<=9;d2++)
for(d3=0;d3<=9;d3++)
palindrome[cnt++]=d1*100000+d2*10000+d3*1000+d3*100+d2*10+d1;
break;
case 7:
for(d1=1;d1<=9;d1+=2)
for(d2=0;d2<=9;d2++)
for(d3=0;d3<=9;d3++)
for(d4=0;d4<=9;d4++)
palindrome[cnt++]=d1*1000000+d2*100000+d3*10000+d4*1000+d3*100+d2*10+d1;
break;
case 8:
for(d1=1;d1<=9;d1+=2)
for(d2=0;d2<=9;d2++)
for(d3=0;d3<=9;d3++)
for(d4=0;d4<=9;d4++)
palindrome[cnt++]=d1*10000000+d2*1000000+d3*100000+d4*10000+d4*1000+d3*100+d2*10+d1;
break;
}
}
bool isPrime(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0)
return false;
}
return true;
}
int main(){
int a,b;
cin >> a >> b;
// time_t begin,end;
// begin=clock();
int da=digit(a),db=digit(b);
if(db<=8)
for(int i=da;i<=db;i++){
create(i);
}
else if(db==9)
for(int i=da;i<=8;i++){
create(i);
}
cout << cnt << endl;
if(a>11)
for(int i=0;i<cnt;i++){
if(palindrome[i]>=a&&palindrome[i]<=b)
if(isPrime(palindrome[i]))
cout << palindrome[i] << endl;
else if(palindrome[i]>b)
break;
}
else{
switch(a){
case 1: case 2: cout << 2 << endl << 3 << endl << 5 << endl << 7 << endl << 11 << endl; break;
case 3: cout << 3 << endl << 5 << endl << 7 << endl << 11 << endl; break;
case 4: case 5: cout << 5 << endl << 7 << endl << 11 << endl; break;
case 6: case 7: cout << 7 << endl << 11 << endl; break;
case 8: case 9: case 10: case 11: cout << 11 << endl; break;
}
for(int i=0;i<cnt;i++){
if(palindrome[i]>=a&&palindrome[i]<=b)
if(isPrime(palindrome[i]))
cout << palindrome[i] << endl;
else if(palindrome[i]>b)
break;
}
}
// end=clock();
// cout<<"runtime: "<<double(end-begin)/CLOCKS_PER_SEC<<endl;
return 0;
}
关于两种算法的复杂度分析，等会再码字。