POJ 1811 Prime Test

Prime Test
Time Limit: 6000MS
 
Memory Limit: 65536K
Total Submissions: 15434
 
Accepted: 2909
Case Time Limit: 4000MS
Description
Given a big integer number, you are required to find out whether it's a prime number.
Input
The first line contains the number of test cases T (1 <= T <= 20 ), then the following T lines each contains an integer number N (2 <= N < 2
54).
Output
For each test case, if N is a prime number, output a line containing the word "Prime", otherwise, output a line containing the smallest prime factor of N.
Sample Input

2
5
10

Sample Output

Prime
2

Source
POJ Monthly
 
/*Miller Robin素性テスト+Pollard rho素因子を探すMiller RobinとPollard rhoの理論は非常に強いと思いますが、詳細はここでは言いませんが、アルゴリズムガイド31章*/#include#include#include#define MAX_を参照してくださいL 64//最長桁数#define TIMES 8//miller robin素性試験の試験回数#define MAX_VAL(pow(2.0,60)//最大値の定義#define CVAL 200 using namespace std;//最小素数_int64 minFactor;//(1)a*b mod nを計算する構想:bのバイナリ表現による分割計算//(2)例えば:b=1011101 a*b mod n=(a*100000 mod n+a*10000 mod n+a*1000 mod n+a*100 mod n+a*100 mod n+a*1 mod n)mod n//(3)構想は上記のように低位から高位へbを遍歴し、aで現在のビットが1の値を記録し、b現在のビットが//1になるたびに結果値にaとmod nを加算し、そしてaは2__を掛けるint 64 multAndMod(_int 64 a,_int 64 b,_int 64 n){a=a%n;_int 64 res=0;while(b){//現在ビット1 if(b&1){////現在ビット値res+=a;//mod n if(res>=n)res-=n;//2を乗じて1ビットa=a<<1;//を上げるmod n if(a >= n) a -= n; b = b >> 1; } return res; }//(1)a^b mod nを計算するには、上記と同様に、bのバイナリ表現を用いて分割計算を行う//(2)例えば、b=1011101でa^b mod n=[(a^100000 mod n)*(a^10000 mod n)*(a^1000 mod n)*(a^100 mod n)*(a^1 mod n)]mod n//(3)構想が上記のようになり、下位から上位へbを遍歴し、現在のビット1の値をaで記録することができるb現在のビットが//1に遭遇するたびに、結果をaおよびmod nに乗算し、aはaを乗算してビット__を上げる.int 64 modAndExp(_int 64 a,_int 64 b,_int 64 n){a=a%n;_int 64 res=1;while(b>=1){//現在のビットに遭遇すると、res*現在のaとmod n if(b&1)res=multAndMod(res,a,n);//a*aは、a=multAndMod(a,a,n);b=b>>1を上げる.return res; }//MillerRobin素性試験,true:素数,flase:合数bool millerRobin(_int 64 a,_int 64 n){_int 64 u=0,cur=n-1;int t=0;bool find 1=false;while(cur!=0){if(!find 1){int pb=cur%2;if(pb=0)t+;else find 1=true;}if(find1) break; cur = cur/2; } u = cur; cur = modAndExp(a, u, n); __int64 now; for(int p = 1; p <= t; p++) { now = modAndExp(cur, 2, n); if(cur != 1 && now == 1 && cur != n - 1) {//printf("%d %d/n", cur, now); return false; } cur = now; } if(cur != 1) {//printf("a:%I64d u:%I64d n:%I64d val:%I64d/n", a, u, n, start); return false; }//printf("a:%I64d u:%I64d n:%I64d val:%I64d/n", a, u, n, start); return true; }//Miller Robinを用いてnのn次素性試験bool testPrime(int times,_int 64 n){if(n==2)return true;if(n%2==0)return false;_int 64 a;int t;srand(time(NULL);for(t=1;t<=times;t+){a=rand()%(n-1)+1;if(!millerRobin(a,n))return false;}return true; } __int64 gcd(__int64 a, __int64 b) { if(b == 0) return (a); return gcd(b, a % b); } __int 64 PollardRho(_int 64 n,int c){int i=1;srand(time(NULL);_int 64 x=rand()%n;_int 64 y=x;int k=2;while(true){i=i+1;x=(modAndExp( x,2,n)+c)%n;_int 64 d=gcd(y−x,n);if(1