POJ 1811 Prime Test

Prime Test

Time Limit: 6000ms

Case Time Limit: 4000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 1811
64-bit integer IO format: %lld Java class name: Main

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 < 254).

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-Rabbin + Pollard-rho

 1 #include <cstdio>
 2 #include <ctime>
 3 #include <cstdlib>
 4 using namespace std;
 5 typedef long long LL;
 6 const int maxn = 1001;
 7 LL mul(LL a,LL b,LL mod) {
 8     if(!a) return 0;
 9     return ((a&1)*b%mod + (mul(a>>1,b,mod)<<1)%mod)%mod;
10 }
11 LL quickPow(LL a,LL d,LL n) {
12     LL ret = 1;
13     while(d) {
14         if(d&1) ret = mul(ret,a,n);
15         d >>= 1;
16         a = mul(a,a,n);
17     }
18     return ret;
19 }
20 bool check(LL a,LL d,LL n) {
21     if(n == a) return true;
22     while(~d&1) d >>= 1;
23     LL t = quickPow(a,d,n);
24     while(d < n-1 && t != 1 && t != n-1) {
25         t = mul(t,t,n);
26         d <<= 1;
27     }
28     return (d&1) || t == n-1;
29 }
30 bool isP(LL n) {
31     if(n == 2) return true;
32     if(n < 2 || 0 == (n&1)) return false;
33     static int p[5] = {2,3,7,61,24251};
34     for(int i = 0; i < 5; ++i)
35         if(!check(p[i],n-1,n)) return false;
36     return true;
37 }
38 LL gcd(LL a,LL b) {
39     if(a < 0) return gcd(-a,b);//特别注意，没这个TLE
40     return b?gcd(b,a%b):a;
41 }
42 LL Pollard_rho(LL n,LL c) {
43     LL i = 1,k = 2,x = rand()%n,y = x;
44     while(true) {
45         x = (mul(x,x,n) + c)%n;
46         LL d = gcd(y - x,n);
47         if(d != 1 && d != n) return d;
48         if(y == x) return n;
49         if(++i == k) {
50             y = x;
51             k <<= 1;
52         }
53     }
54 }
55 LL Fac[maxn],tot;
56 void factorization(LL n) {
57     if(isP(n)) {
58         Fac[tot++] = n;
59         return;
60     }
61     LL p = n;
62     while(p >= n) p = Pollard_rho(p,rand()%(n-1)+1);
63     factorization(p);
64     factorization(n/p);
65 }
66 int main() {
67     int kase;
68     LL x;
69     scanf("%d",&kase);
70     while(kase--) {
71         scanf("%I64d",&x);
72         if(isP(x)) puts("Prime");
73         else {
74             tot = 0;
75             LL ret = x;
76             factorization(x);
77             for(int i = 0; i < tot; ++i)
78                 if(ret > Fac[i]) ret = Fac[i];
79             printf("%I64d
",ret);
80         }
81     }
82     return 0;
83 }

View Code