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 )

&nbspreturn 1;

f = mpow( s, t >> 1, m );

if ( t & 1 )

{

&nbspp = s * f * f;

&nbspreturn p % m;

}

p = f * f;

return p % m;

}

int Miller_Ribin( int s )

{

int i, p;

for ( i = 0; i < 3; i++ )

{

&nbspp = rand()% ( s - 2 ) + 2;

&nbspif ( 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 )

{

&nbspif ( a <= 3 && b >= 3 )

printf("3\n");

&nbspif ( a <= 5 && b >= 5 )

printf("5\n");

&nbspif ( a <= 7 && b >= 7 )

printf("7\n");

&nbspreturn ;

}

for ( i = 0; i < p; i++ )

&nbsps *= 10;

for ( i = 1; i < 10; i += 2 )

{

&nbspfor ( j = 0; j < s; j++ )

{

r = i * s + j;

t1 = j / 10;

t2 = p - 1;

while ( t2 )

{

&nbspr = r * 10 + ( t1 % 10 );

&nbspt1 /= 10;

&nbspt2--;

}

r = r * 10 + i;

if ( r < a )

&nbspcontinue;

if ( r > b )

&nbspreturn ;

if ( Miller_Ribin( r ) )

&nbspprintf("%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 )

{

&nbspc++;

&nbspp *= 10;

}

p /= 10;

while ( p < b )

{

&nbspif ( c == 2 )

printf("11\n");

&nbspif ( c & 1 )

work( c );

&nbspc++;

&nbspp *= 10;

}

printf("force program runs %.3lfs\n", clock( ) / (double)

◆◆

评论读取中....

请登录后再发表评论!

◆◆

修改失败，请稍后尝试