Question

如何提高c语言判断回文素数效率?

要求打出3~1000000000范围的回文素数,并显示用时,且在30秒内.我的严重超时,请高手指点~我自己的程序如下:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
/*判断是否回文*/

int hw(int num)
{
int n=0;
int count=0;
count=num;

do
{
n*=10;
n+=num%10;
num/=10;

}
while (num>0);

if (count==n)
{
return 1;
}
else
{
return 0;

}

}

/*判断是否素数*/
int ss(int num)
{
int i,k,flag;
k=(int)sqrt(num);
for (i=3;i<=k;i+=2)
{
if (num%i!=0)
{
continue;
}
else
{
flag=0;
break;
}
}
if (i==(k+1))
flag=1;
return flag;

}

int main()
{
int start=3,end=1000000000,b;
int s,e;
s=time(NULL);

for (b=start;b<=end;b=b+2)
{

if (hw(b))
{
if (ss(b))
{
printf("%d\n",b);
}
}

}
e=time(NULL);
printf(" %d seconds",e-s);
return 0;
}
或是构造输出3~1e9的回文素数也可

Answer 1

0.210秒，用Miller-Ribin检验素数
在oj上是15ms
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

int a, b;

int mpow( int s, int t, int m )
{
long long f, p;
if ( t == 0 )
    return 1;
f = mpow( s, t >> 1, m );
if ( t & 1 )
{
    p = s * f * f;
    return p % m;
}
p = f * f;
return p % m;
}

int Miller_Ribin( int s )
{
int i, p;
for ( i = 0; i < 3; i++ )
{
    p = rand()% ( s - 2 ) + 2;
    if ( mpow( p, s - 1, s ) != 1 )
     break;
}
return i == 3;
}

void work( int c )
{
int p = ( c - 1 ) >> 1, i, j, s = 1, r, t1, t2;
if ( c == 1 )
{
    if ( a <= 3 && b >= 3 )
     printf("3\n");
    if ( a <= 5 && b >= 5 )
     printf("5\n");
    if ( a <= 7 && b >= 7 )
     printf("7\n");
    return ;
}
for ( i = 0; i < p; i++ )
    s *= 10;
for ( i = 1; i < 10; i += 2 )
{
    for ( j = 0; j < s; j++ )
    {
     r = i * s + j;
     t1 = j / 10;
     t2 = p - 1;
     while ( t2 )
     {
        r = r * 10 + ( t1 % 10 );
        t1 /= 10;
        t2--;
     }
     r = r * 10 + i;
     if ( r < a )
        continue;
     if ( r > b )
        return ;
     if ( Miller_Ribin( r ) )
        printf("%d\n", r);
    }
}
}

int main( )
{
int s, e;
srand( time( NULL ) );
int i, p, c;
// scanf("%d%d", &a, &b);
a = 3; b = 1000000000;
p = 1;
c = 0;
while ( p < a )
{
    c++;
    p *= 10;
}
p /= 10;
while ( p < b )
{
    if ( c == 2 )
     printf("11\n");
    if ( c & 1 )
     work( c );
    c++;
    p *= 10;
}
printf("force program runs %.3lfs\n", clock( ) / (double)

CLK_TCK);
return 0;
}

Answer 2

时间仓促，写了一个代码，在P42.0G/512M/WIN2003/BCB2007的环境中用时50s

算法描述：开头是2，4，5，6，8的数字可以直接略过不予考虑，这样可以节省时间，先找回文数，然后再找素数。

程序如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define N 1000
long x=3;
int tc(long int *s)
{

int i;
for (i=0; i <N ; i++) s[i]=x++;

return 1;

}
int zs(long int s)
{
long int sq,j;

sq=sqrt(s);
for (j=2; j<=sq; j++) {
if (s%j==0) {
return 0;
}
}
return 1;
}
void h(long int *s)
{
int i,j,len,len2;
char a[10];
for (i = 0; i<N; i++) {
sprintf(a,"%d",s[i]);

len=strlen(a);

len2=len/2;
for (j=0; j<len2; j++)
if (a[j]!=a[len-j-1]) {
s[i]=0;
break;
}

}

}
void z(long int *s)
{
int i;
long int sq,j;
for (i = 0; i<N; i++) {
if (s[i]!=0){
sq=sqrt(s[i]);
for (j=2; j<=sq; j++)
if (s[i]%j==0) {
s[i]=0;
break;
}

}

}
}
void p(long int *s)
{
int i;
int count=1;
for (i = 0; i<N; i++) {
if (s[i]!=0) {
printf("%ld",s[i]);
putchar(++count%10==0?'\n':' ');
}

}
}
void main()
{
time_t l_time;
long int l,l1;
long int s[N];
char a[10];

l_time=time(0);

for (l=1; l <= 100000; l++) {

if (x>9) {
sprintf(a,"%d",x+100);
l1=a[0]-48;
if (l1%2==0||l1%5==0) {x+=1000;continue;}
}

tc(s);

h(s);
z(s);
p(s);

}
l_time=time(0)-l_time;
printf("\n\n%ld sec.\n",l_time);
system("pause");

}

Answer 3

其他的先不说
int start=3,end=1000000000,b;
for (b=start;b<=end;b=b+2)

整型能表示1000000000这么大的数吗

一共就能放65536个

Answer 4

32位字长的机器int型能取到2147483647，所以这个题用int 是没有问题的。

在回文的生成了，优化下代码~！

晕，有点问题了~！

期待高手的解决：我的也跑了N久才

Answer 5

用long吧，4294967296的最大值