用c语言如何判断素数
来源：学生作业帮助网 编辑：六六作业网 时间：2024/05/11 15:26:11
用c语言如何判断素数
用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\n");
if ( a = 5 )
printf("5\n");
if ( a = 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)