UC知道如何提高c语言判断回文素数效率?
来源：百度知道 编辑：UC知道 时间：2024/05/16 07:57:33
要求打出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;
}
<
#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;
}
<
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 &