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

Source

POJ Monthly

题目大意：T组数据，对于输入的N，若N为素数，输出"Prime"，否则输出N的最小素因子

思路：由于N的规模为2^54所以普通的素性推断果断过不了。

要用Miller Rabin素数測试来做。

而若N不为素数。则须要对N进行素因子分解。由于N为大数，考虑用Pollar Rho整数分解来做。

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#include<math.h>

#define MAX_VAL (pow(2.0,60))

//miller_rabbin素性測试

//__int64 mod_mul(__int64 x,__int64 y,__int64 mo)

//{

//    __int64 t;

//    x %= mo;

//    for(t = 0; y; x = (x<<1)%mo,y>>=1)

//        if(y & 1)

//            t = (t+x) %mo;

//

//    return t;

//}

__int64 mod_mul(__int64 x,__int64 y,__int64 mo)

{

    __int64 t,T,a,b,c,d,e,f,g,h,v,ans;

    T = (__int64)(sqrt(double(mo)+0.5));

    t = T*T - mo;

    a = x / T;

    b = x % T;

    c = y / T;

    d = y % T;

    e = a*c / T;

    f = a*c % T;

    v = ((a*d+b*c)%mo + e*t) % mo;

    g = v / T;

    h = v % T;

    ans = (((f+g)*t%mo + b*d)% mo + h*T)%mo;

    while(ans < 0)

        ans += mo;

    return ans;

}

__int64 mod_exp(__int64 num,__int64 t,__int64 mo)

{

    __int64 ret = 1, temp = num % mo;

    for(; t; t >>=1,temp=mod_mul(temp,temp,mo))

        if(t & 1)

            ret = mod_mul(ret,temp,mo);

    return ret;

}

bool miller_rabbin(__int64 n)

{

    if(n == 2)

        return true;

    if(n < 2 || !(n&1))

        return false;

    int t = 0;

    __int64 a,x,y,u = n-1;

    while((u & 1) == 0)

    {

        t++;

        u >>= 1;

    }

    for(int i = 0; i < 50; i++)

    {

        a = rand() % (n-1)+1;

        x = mod_exp(a,u,n);

        for(int j = 0; j < t; j++)

        {

            y = mod_mul(x,x,n);

            if(y == 1 && x != 1 && x != n-1)

                return false;

            x = y;

        }

        if(x != 1)

            return false;

    }

    return true;

}

//PollarRho大整数因子分解

__int64 minFactor;

__int64 gcd(__int64 a,__int64 b)

{

    if(b == 0)

        return a;

    return gcd(b, a % b);

}

__int64 PollarRho(__int64 n, int c)

{

    int i = 1;

    srand(time(NULL));

    __int64 x = rand() % n;

    __int64 y = x;

    int k = 2;

    while(true)

    {

        i++;

        x = (mod_exp(x,2,n) + c) % n;

        __int64 d = gcd(y-x,n);

        if(1 < d && d < n)

            return d;

        if(y == x)

            return n;

        if(i == k)

        {

            y = x;

            k *= 2;

        }

    }

}

void getSmallest(__int64 n, int c)

{

    if(n == 1)

        return;

    if(miller_rabbin(n))

    {

        if(n < minFactor)

            minFactor = n;

        return;

    }

    __int64 val = n;

    while(val == n)

        val = PollarRho(n,c--);

    getSmallest(val,c);

    getSmallest(n/val,c);

}

int main()

{

    int T;

    __int64 n;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%I64d",&n);

        minFactor = MAX_VAL;

        if(miller_rabbin(n))

            printf("Prime\n");

        else

        {

            getSmallest(n,200);

            printf("%I64d\n",minFactor);

        }

    }

    return 0;

}