POJ 1811 Prime Test(Miller-Rabin & Pollard-rho素数测试)

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 < 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.
 
题目大意:给一个数n,问是不是素数,若是输出Prime,若不是输出其最小的非1因子。
思路:http://www.2cto.com/kf/201310/249381.html
模板盗自:http://vfleaking.blog.163.com/blog/static/1748076342013231104455989/
 
代码(375MS):
 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iterator>
#include <vector>
using namespace std; typedef long long LL; LL modplus(LL a, LL b, LL mod) {
LL res = a + b;
return res < mod ? res : res - mod;
} LL modminus(LL a, LL b, LL mod) {
LL res = a - b;
return res >= ? res : res + mod;
} LL mult(LL x, LL p, LL mod) {
LL res = ;
while(p) {
if(p & ) res = modplus(res, x, mod);
x = modplus(x, x, mod);
p >>= ;
}
return res;
} LL power(LL x, LL p, LL mod) {
LL res = ;
while(p) {
if(p & ) res = mult(res, x, mod);
x = mult(x, x, mod);
p >>= ;
}
return res;
} bool witness(LL n, LL p) {
int t = __builtin_ctz(n - );
LL x = power(p % n, (n - ) >> t, n), last;
while(t--) {
last = x, x = mult(x, x, n);
if(x == && last != && last != n - ) return false;
}
return x == ;
} const int prime_n = ;
int prime[prime_n] = {, , , , }; bool isPrime(LL n) {
if(n == ) return false;
if(find(prime, prime + prime_n, n) != prime + prime_n) return true;
if(n % == ) return false;
for(int i = ; i < prime_n; i++)
if(!witness(n, prime[i])) return false;
return true;
} LL getDivisor(LL n) {
int c = ;
while (true) {
int i = , k = ;
LL x1 = , x2 = ;
while(true) {
x1 = modplus(mult(x1, x1, n), c, n);
LL d = __gcd(modminus(x1, x2, n), n);
if(d != && d != n) return d;
if(x1 == x2) break;
i++;
if(i == k) x2 = x1, k <<= ;
}
c++;
}
} void getFactor(LL n, vector<LL> &ans) {
if(isPrime(n)) return ans.push_back(n);
LL d = getDivisor(n);
getFactor(d, ans);
getFactor(n / d, ans);
} int main() {
int T; LL n;
scanf("%d", &T);
while(scanf("%I64d", &n) != EOF) {
if(isPrime(n)) puts("Prime");
else {
vector<LL> ans;
getFactor(n, ans);
printf("%I64d\n", *min_element(ans.begin(), ans.end()));
}
}
}
上一篇:linux搭建maven私服


下一篇:2016 Al-Baath University Training Camp Contest-1 B