poj 1811 Prime Test、ランダム素数テスト
3357 ワード
Prime Test
Time Limit: 6000MS
Memory Limit: 65536K
Total Submissions: 24514
Accepted: 5730
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
Sample Output
Miller_Rabinアルゴリズム
Time Limit: 6000MS
Memory Limit: 65536K
Total Submissions: 24514
Accepted: 5730
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
Miller_Rabinアルゴリズム
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
// rand(void) [0,RAND_MAX] 。
//random(n) [0,n]
ll random(ll n) {
return (ll)((double)rand()/RAND_MAX*n + 0.5);
}
inline ll mul_mod(ll a, ll b, ll c) {
ll res = 0;
a %= c;
b %= c;
for(; b; b>>= 1, a=(a<<1)%c) {
if(b&1) res = (res+a)%c;
}
return res;
}
ll pow_mod(ll a, ll b, ll c) {
ll res = 1;
for(; b; b>>=1, a=mul_mod(a,a,c)) {
if(b&1) res = mul_mod(res, a, c);
}
return res;
}
bool check(ll a, ll n, ll x, ll t) {
ll ret = pow_mod(a, x, n);
ll last = ret;
for(int i=1; i<=t; ++i) {
ret = mul_mod(ret, ret, n);
if(ret==1 && last!=1 && last!=n-1) return true;
last = ret;
}
if(ret!=1) return true;
else return false;
}
const int N = 8;
bool miller_rabin(ll n) {
if(n<2) return false;
if(n==2) return true;
if( (n&1)==0) return false;
ll x = n-1;
ll t = 0;
while( (x&1)==0 ) {
x >>= 1;
t++;
}
for(int i=0; i< N; ++i) {
ll a = random(x-2) + 1;
if( check(a,n,x,t) )
return false;
}
return true;
}
ll factor[100];
int tol;
ll gcd(ll a, ll b) {
return b?gcd(b,a%b): a>=0?a:-a;
}
ll pollard_rho(ll x, ll c) {
ll i=1, k=2;
ll x0 = random(x-2) + 1;
ll y = x0;
while(1) {
i++;
x0 = (mul_mod(x0,x0,x) + c) % x;
ll d = gcd(y-x0, x);
if(d != 1 && d != x) return d;
if(y == x0) return x;
if(i == k) {
y = x0;
k += k;
}
}
}
void findfac(ll n, int k) {
if(n==1) return ;
if(miller_rabin(n)) {
factor[tol++] = n;
return ;
}
ll p = n;
int c = k;
while(p >= n) p = pollard_rho(p, c--);
findfac(p, k);
findfac(n/p, k);
}
int main() {
int T;
ll n;
// srand(time(NULL));
//POJ G++ , 。。
scanf("%d", &T);
while(T--) {
scanf("%lld", &n);
if(miller_rabin(n)) {
printf("Prime
");
} else {
tol = 0;
findfac(n, 107);
ll ans = factor[0];
for(int i=1; i<tol; ++i)
if(ans > factor[i])
ans = factor[i];
printf("%lld
", ans);
}
}
return 0;
}