POJ1811(SummerTrainingDay04-G miller-rabin判断素性 && pollard-rho分解质因数)

Prime Test

Time Limit: 6000MS		Memory Limit: 65536K
Total Submissions: 35528		Accepted: 9479
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 //2017-08-16
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 #define ll long long
  7 
  8 using namespace std;
  9 
 10 const int TIMES = 10;
 11 
 12 ll random0(ll n){
 13     return ((double)rand() / RAND_MAX*n + 0.5);
 14 }
 15 
 16 //快速乘a*b%mod
 17 ll quick_mul(ll a, ll b, ll mod){
 18     ll ans = 0;
 19     while(b){
 20         if(b&1){
 21             b--;
 22             ans = (ans+a)%mod;
 23         }
 24         b >>= 1;
 25         a = (a+a) % mod;
 26     }
 27     return ans;
 28 }
 29 
 30 //快速幂a^b%mod
 31 ll quick_pow(ll a, ll n, ll mod){
 32     ll ans = 1; 
 33     while(n){
 34         if(n&1)ans = quick_mul(ans, a, mod);
 35         a = quick_mul(a, a, mod);
 36         n >>= 1;
 37     }
 38     return ans;
 39 }
 40 
 41 bool witness(ll a, ll n){
 42     ll tmp = n-1;
 43     int i = 0;
 44     while(tmp % 2 == 0){
 45         tmp >>= 1;
 46         i++;
 47     }
 48     ll x = quick_pow(a, tmp, n);
 49     if(x == 1 || x == n-1)return true;
 50     while(i--){
 51         x = quick_mul(x, x, n);
 52         if(x == n-1)return true;
 53     }
 54     return false;
 55 }
 56 
 57 bool miller_rabin(ll n){
 58     if(n == 2)return true;
 59     if(n < 2 || n % 2 == 0)return false;
 60     for(int i  = 1; i <= TIMES; i++){
 61         ll a = random0(n-2)+1;
 62         if(!witness(a, n))
 63               return false;
 64     }
 65     return true;
 66 }
 67 
 68 //factor存放分解出来的素因数
 69 ll factor[1000];
 70 int tot;
 71 
 72 ll gcd(ll a, ll b){
 73     if(a == 0)return 1;
 74     if(a < 0)return gcd(-a, b);
 75     while(b){
 76         ll tmp = a % b;
 77         a = b;
 78         b = tmp;
 79     }
 80     return a;
 81 }
 82 
 83 ll pollard_rho(ll x, ll c){
 84     ll i = 1, k = 2;
 85     ll x0 = rand()%x, x1 = x0;
 86     while(1){
 87         i++;
 88         x0 = (quick_mul(x0, x0, x)+c)%x;
 89         ll d = gcd(x1-x0, x);
 90         if(d != 1 && d != x)return d;
 91         if(x1 == x0)return x;
 92         if(i == k){
 93             x1 = x0;
 94             k += k;
 95         }
 96     }
 97 }
 98 
 99 //对n分解质因数
100 void decomposition_factor(ll n){
101     if(miller_rabin(n)){
102         factor[tot++] = n;
103         return;
104     }
105     ll p = n;
106     while(p >= n){
107         p = pollard_rho(p, rand()%(n-1)+1);
108     }
109     decomposition_factor(p);
110     decomposition_factor(n/p);
111 }
112 
113 int main()
114 {
115     int T;
116     scanf("%d", &T);
117     while(T--){
118         ll n;
119         scanf("%lld", &n);
120         if(miller_rabin(n))
121               printf("Prime
");
122         else{
123             tot = 0;
124             decomposition_factor(n);
125             ll ans = factor[0];
126             for(int i = 1; i < tot; i++)
127                   if(factor[i] < ans)ans  = factor[i];
128             printf("%lld
", ans);
129         }
130     }
131 
132     return 0;
133 }