POJ 1811 Prime Test素性試験分解素因子

タイトル:
n(n<=2^54)を数えて、nが素数かどうかを判断して、出力Primeであれば、そうでなければnの最小の素数を出力します.
問題解決の考え方:
自然数素性試験はMatrix 67の素数と素性テストを見ることができます
素因数分解はPollard rho因数分解を利用しており、Pollard rho因数分解参照
コードを保存~
 

/* **********************************************

Author      : JayYe

Created Time: 2013-9-25 16:02:25

File 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
", ans);

        }

    }

    return 0;

}