这是100000000内求回文素数的算法,谁能帮忙优化下~

发布网友发布时间：2022-05-06 04:06

共3个回答

热心网友时间：2022-06-28 16:40

//回文
int palindromic( unsigned long dat )
{
unsigned char buf[20]; //64位2进制最长20位10进制
int i,len;
//10进制取出
len = 0;
while( dat > 0 && len < sizeof(buf) )
{
buf[ len++ ] = dat % 10;
dat /= 10;
}
//判断回文
i = 0;
while( i < len )
if( buf[ i++ ] != buf[ --len ] )
return 0;
return 1;
}

//质数(素数)
int prime( unsigned long dat )
{
unsigned long k;
if( !(dat & 0x01 ) && dat != 2 ) //偶数非质数(2例外)
return 0;
for( k=3; k < dat/2; k+=2 ) //因子为偶的情况已经在上一句程序剔除
{
if( !(dat % k ))
return 0;
}
return 1; //质数
}

int main()
{
unsigned long i;
for(i=1; i<9999999; ++i)
if( prime(i) )
if( palindromic(i) )
printf("%d,", i);
}

热心网友时间：2022-06-28 16:40

有一种方法是不使用质数表,直接穷举所有10^4内的数字,然后用这个数字"翻折对称"得到一个待试数A,然后利用费马小定理快速判断是否为质数.这样时空复杂度都低了,不过费马小定理的那种判断质数法好像有几个特例需要手动判断,具体可以查看该回答的"参考资料"

参考资料：http://www.cnblogs.com/Knuth/archive/2009/09/04/1559949.html

热心网友时间：2022-06-28 16:41

void prime()len=strlen(tem);
for(k=0