用c语言如何判断素数

题目

用c语言如何判断素数

答案

0.210秒,用Miller-Ribin检验素数
在oj上是15ms
#include
#include
#include
#include
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 )
printf("3 ");
 if ( a = 5 )
printf("5 ");
 if ( a = 7 )
printf("7 ");
 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 ",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 ");
 if ( c & 1 )
work( c );
 c++;
 p *= 10;
}
printf("force program runs %.3lfs ",clock( ) / (double)