#include <stdio.h>
#include <time.h>
#include <stdlib.h>

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 < 10; i++ )
{
p = rand()% ( s - 1 ) + 1;
if ( mpow( p, s - 1, s ) != 1 )
break;
}
return i == 10;
}

int main( )
{
srand( time( NULL ) );
int x;
printf("请输入数: ");
scanf("%d", &x);
if ( x < 0 )
x = -x;
if ( x <= 1 )
printf("该数不是素数\n");
else
if ( Miller_Ribin( x ) )
printf("该数是素数\n");
else
printf("该数不是素数\n");
return 0;
}

[此贴子已经被作者于2007-11-15 15:58:45编辑过]