POJ 1811 Prime Test 素性测试 分解素因子

题意：

给你一个数n(n <= 2^54)，判断n是不是素数，如果是输出Prime，否则输出n最小的素因子

解题思路：

自然数素性测试可以看看Matrix67的 素数与素性测试

素因子分解利用的是Pollard rho因数分解，可以参考 Pollard rho因数分解

存个代码~

/* **********************************************Author      : JayYeCreated Time: 2013-9-25 16:02:25File Name   : JayYe.cpp*********************************************** */#include <stdio.h>#include <string.h>#include <time.h>#include <algorithm>using namespace std;#define Time 12 // Miller测试次数typedef __int64 ll;const ll INF = 1LL << 61;const int maxC = 240;ll big_mul(ll a, ll b, ll n) {    ll ret = 0;    a %= n;    while(b) {        if(b & 1) {            ret += a;            if(ret >= n)    ret -= n;        }        a *= 2;        if(a >= n)  a -= n;        b /= 2;    }    return ret;}ll pow_mod(ll x, ll n, ll m) {    ll ret = 1;    x %= n;    while(n) {        if(n & 1)   ret = big_mul(ret, x, m);        x = big_mul(x, x, m);        n /= 2;    }    return ret;}// 以a为基对n进行Miller次测试并进行二次探测，返回true则是合数bool Wintess(ll a, ll n) {    ll m = n-1;    int top = 0;    // n-1 = m*(2^top)    while(m % 2 == 0) {        m /= 2;        top++;    }    ll x = pow_mod(a, m, n), y;    for(int i = 0;i < top; i++) {        y = big_mul(x, x, n);        if(y == 1 && (x != 1 && x != n-1))            return true;        x = y;    }    if(y > 1)   return true;    return false;}// 对n进行ts次 Miller素性测试bool Miller_Rabin(int ts, ll n) {    if(n == 2)  return true;    if(n == 1 || n % 2 == 0)  return false;    srand(time(NULL));    for(int i = 0;i < ts; i++) {        ll a = rand() % (n-1) + 1;        if(Wintess(a, n))   return false;    }    return true;}ll ans;ll gcd(ll a, ll b) {    return b ? gcd(b, a%b) : a;}// 对n进行因式分解，找出n的一个因子，该因子不一定是最小的ll Pollard(ll n, int c) {    srand(time(NULL));    ll i = 1, k = 2, x = rand()%n, y = x;    while(true) {        i++;        x = (big_mul(x, x, n) + c) % n;        ll d = gcd(y - x, n);        if(d > 1 && d < n)  return d;        if(y == x)  return n; // 如果该数已经出现过，直接返回        if(i == k) {            y = x; k <<= 1;        }    }}// 找出所有素因子void solve(ll n, int c) {    if(n == 1)  return ;    // 判断是否为素数    if(Miller_Rabin(Time, n)) {        if(ans > n) ans = n;        return ;    }    ll m = n;    while(m == n) {   // 找出n的一个因子        m = Pollard(n, c--);    }    solve(m, c);    solve(n/m, c);}int main() {    int t;    ll n;    scanf("%d", &t);    while(t--) {        scanf("%I64d", &n);        if(Miller_Rabin(Time, n))            puts("Prime");        else {            ans = INF;            solve(n, maxC);            printf("%I64d\n", ans);        }    }    return 0;}