#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<time.h>
using namespace std;
typedef unsigned long long llu;
int p[] = { 2,3,5,7,11, 13,17,19,23,29 };
int k = 10;
llu mol_mult( llu a,llu b,const llu &mol)
{
llu c = a >> 30 , d = b >> 30 , tmp , t;
tmp = 1ll << 30;
a %= tmp ; b %= tmp;
llu ans = a * b;
if( ans > mol )
ans %= mol;
tmp = c * b ;
if( tmp > mol ) tmp %= mol;
t = 30;
while( t -- ){
tmp <<= 1;
if( tmp > mol ) tmp -= mol;
}
ans += tmp;
if( ans > mol )
ans -= mol;
tmp = d * a ;
if( tmp > mol ) tmp %= mol;
t = 30;
while( t -- ){
tmp <<= 1;
if( tmp > mol ) tmp -= mol;
}
ans += tmp;
if( ans > mol )
ans -= mol;
tmp = d * c ;
if( tmp > mol ) tmp %= mol;
t = 60;
while( t -- ){
tmp <<= 1;
if( tmp > mol ) tmp -= mol;
}
ans += tmp;
ans %= mol;
return ans;
}
llu mol_exp( llu a,llu b,llu n)
{
llu t = a % n , ans = 1;
while( b )
{
if( b & 1 )
{
ans = mol_mult( ans, t, n);//1ll * ans * t % n;
}
t = mol_mult( t, t, n );//1ll * t * t % n;
b >>= 1;
}
return ans;
}
int witness( llu a,llu n )
{
llu t = 0, tmp = n - 1;
while( tmp % 2 == 0 ){
t ++ ;
tmp >>= 1 ;
}
llu x0 = mol_exp( a, tmp, n ), x1, i;
for ( i = 1 ; i <= t ; i ++ )
{
x1 = mol_mult( x0, x0 , n);//1ll * x0 * x0 % n;
if( x1 == 1 && x0 != 1&& x0 != n - 1 )
return 1;
x0 = x1;
}
if( x1 != 1 )
return 1;
return 0;
}
llu my_rand(llu b,llu e )
{
return (llu)((1. * rand() / ( 1. + RAND_MAX ) * (e - b + 1))) + b;
}
int miller_rabin( llu n,llu s )
{
llu i, a;
for ( i = 1 ; i <= s ; i ++ )
{
a = my_rand( 2, n - 1);
if( witness ( a, n ) ) return 0;
}
return 1;
}
int main()
{
llu n, i;
srand( n );
while( scanf("%llu",&n) != EOF )
{
if( n == 1 ){ puts("It is not a prime number."); continue; }
for ( i = 0 ; i < k ; i ++ )
if( n % p[i] == 0 ){
printf("%s\n", n == p[i] ? "It is a prime number.":"It is not a prime number." );
break;
}
if( i < k ) continue;
if( miller_rabin( n, 1 ) )
printf("It is a prime number.\n");
else
printf("It is not a prime number.\n");
}
return 0;
}
posted on 2009-08-19 21:23
Huicpc217 阅读(350)
评论(0) 编辑 收藏 引用 所属分类:
数论 、
模板