poj 1811 Prime Test 大数素数测试+大数因子分解

Prime Test

Time Limit: 6000MS		Memory Limit: 65536K
Total Submissions: 27129		Accepted: 6713
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⁵⁴).

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

  1 /*
  2 给你一个大数，如果是素数输出prime，如果不是，则输出其最小的质因子。
  3 
  4 利用Miller-Rabbin素数测试和Pollar-rho因数分解可以AC这道题
  5 
  6 */
  7 
  8 
  9 #include<iostream>
 10 #include<cstdio>
 11 #include<string.h>
 12 #include<time.h>
 13 #include<algorithm>
 14 using namespace std;
 15 
 16 typedef __int64 LL;
 17 //****************************************************************
 18 // Miller_Rabin 算法进行素数测试
 19 //速度快，而且可以判断 <2^63的数
 20 //****************************************************************
 21 const int S=20;//随机算法判定次数，S越大，判错概率越小
 22 
 23 
 24 LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63
 25 {
 26     a%=mod;
 27     b%=mod;
 28     LL ans=0;
 29     while(b)
 30     {
 31         if(b&1)
 32         {
 33             ans=ans+a;
 34             if(ans>=mod)
 35             ans=ans-mod;
 36         }
 37         a=a<<1;
 38         if(a>=mod) a=a-mod;
 39         b=b>>1;
 40     }
 41     return ans;
 42 }
 43 
 44 LL pow_mod(LL a,LL b,LL mod) // a^b%mod
 45 {
 46     LL ans=1;
 47     a=a%mod;
 48     while(b)
 49     {
 50         if(b&1)
 51         {
 52             ans=mult_mod(ans,a,mod);
 53         }
 54         a=mult_mod(a,a,mod);
 55         b=b>>1;
 56     }
 57     return ans;
 58 }
 59 
 60 //以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
 61 //一定是合数返回true,不一定返回false
 62 
 63 bool check(LL a,LL n,LL x,LL t)
 64 {
 65     LL ret=pow_mod(a,x,n);
 66     LL last=ret;
 67     for(int i=1;i<=t;i++)
 68     {
 69         ret=mult_mod(ret,ret,n);
 70         if(ret==1 && last!=1 && last!=n-1) return true;//合数
 71         last=ret;
 72     }
 73     if(ret!=1) return true;
 74     else return false;
 75 }
 76 
 77 // Miller_Rabin()算法素数判定
 78 //是素数返回true.(可能是伪素数，但概率极小)
 79 //合数返回false;
 80 
 81 bool Miller_Rabin(long long n)
 82 {
 83     if(n<2)return false;
 84     if(n==2) return true;
 85     if( (n&1)==0) return false;//偶数
 86     LL x=n-1;
 87     LL t=0;
 88     while( (x&1)==0 ) { x>>=1;t++;}
 89     for(int i=0;i<S;i++)
 90     {
 91         LL a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
 92         if(check(a,n,x,t))
 93         return false;//合数
 94     }
 95     return true;
 96 }
 97 
 98 //************************************************
 99 //pollard_rho 算法进行质因数分解
100 //************************************************
101 
102 LL factor[100];//质因数分解结果（刚返回时是无序的）
103 int tol;////质因数的个数。数组小标从0开始
104 
105 LL gcd(LL a,LL b)
106 {
107     if(a==0) return 1;//  !!!!
108     if(a<0)  return gcd(-a,b);
109     while(b)
110     {
111         LL t=a%b;
112         a=b;
113         b=t;
114     }
115     return a;
116 }
117 
118 LL Pollard_rho(LL x,LL c)
119 {
120     LL i=1,k=2;
121     LL x0=rand()%x;
122     LL y=x0;
123     while(1)
124     {
125         i++;
126         x0=(mult_mod(x0,x0,x)+c)%x;
127         LL d=gcd(y-x0,x);
128         if(d!=1 && d!=x) return d;
129         if(y==x0) return x;
130         if(i==k) {y=x0;k+=k;}
131     }
132 }
133 
134 //对n进行素因子分解
135 
136 void findfac(LL n)
137 {
138     if(Miller_Rabin(n))
139     {
140         factor[tol++]=n;
141         return;
142     }
143     LL p=n;
144     while(p>=n)
145     p=Pollard_rho(p,rand()%(n-1)+1);
146     findfac(p);
147     findfac(n/p);
148 }
149 
150 int main()
151 {
152     // srand(time(NULL));//需要time.h头文件  //POJ上G++要去掉这句话
153     int T;
154     LL n;
155     scanf("%d",&T);
156     while(T--)
157     {
158         scanf("%I64d",&n);
159         if(Miller_Rabin(n))
160         {
161             printf("Prime
");
162             continue;
163         }
164         tol=0;
165         findfac(n);// 对n的素数分解
166         LL ans=factor[0];
167         for(int i=1;i<tol;i++)
168         if(factor[i]<ans)
169         ans=factor[i];
170         printf("%I64d
",ans);
171 
172 
173         for(int i=0;i<tol;i++)
174         printf("%I64d ",factor[i]);
175         printf("
");
176     }
177     return 0;
178 }