前天一朋友给了个简单的算法题，说是奥林匹克计算机比赛上的
回文10亿内的素数
要求：
1 可用任何语言
2 内存使用不能超过6M
3 运行不能超过15秒
当时第一就想到了这样：
#include <iostream.h>
using nameplace std;
int main()
{
unsigned long itotal=2;
unsigned long itemp;
unsigned long icount=0;
bool bflag=false;
for(bflag=true;itotal<=1000000000;itotal++)
for(itemp=2;itemp<itotal;itemp++)
if((itotal%itemp)!=0)
;
else
{
bflag=false;
break;
}
if(bflag=true)
icount++;
cout << "Result:" << icount << endl ;
return 0;
}
后来一看他的要求就傻眼了，切不说内存使用，光是运行时间，普通的电脑半个月能运行完都不错了。
后来和朋友讨论了一下，想了半天写出如下代码：
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long INT;
INT ntMap[] = {1,101,10001,1000001,100000001};
INT nPow10[] = {1,10,100,1000,10000,};
int isPrime(INT n)
{
if (n<2) return 0;
if (n%2==0) return 0;
if (n%3==0) return 0;
{
INT nAdd[2] = {4,2};
INT nSq = (INT)sqrt((double)n);
for (INT i=5,a=0; i<=nSq; i+=nAdd[++a&1])
{
if (n%i==0) return 0;
}
}
return 1;
}
void dfs(int nMax, INT sum=0, int ndeep=0)
{
if (nMax<ndeep)
{
if (isPrime(sum))
printf("%d,", sum);
}else for (int n=0; n<10; ++n)
{
dfs(nMax, sum + ntMap[ndeep]*nPow10[nMax-ndeep]*n, ndeep+1);
}
}
int main()
{
for (int n=0; n<4; ++n)
{
dfs(n);
}
return 0;
}
写完后总感觉不够完美，请大家指教
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
