poj 1811解題報告

Prime Test

Time Limit: 6000MS	Memory Limit: 65536K
Total Submissions: 17747	Accepted: 3644
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
      

這道題就是miiler_rabin素數測試和pollard_rho質因子分解的标準模闆題。。。第一次做這樣的題，這道題我是參照網上别人的代碼寫的，作為學習，當做模闆學習了.....

代碼：

語言：c++

#include<ctime>

#include<iostream>

using namespace std;

long long factor[100],fac_top = -1;

//計算兩個數的gcd

long long gcd(long long a,long long b)

{

if(a==0)

return b;

long long c;

while(b!=0)

{

c=b;

b=a%b;

a=c;

}

return a;

}

//ret = (a*b)%n (n<2^62)

long long muti_mod(long long a,long long b,long long n)

{

long long exp = a%n, res = 0;

while(b)

{

if(b&1)

{

res += exp;

if(res>n) res -= n;

}

exp <<= 1;

if(exp>n)

exp -= n;

b>>=1;

}

return res;

}

// ret = (a^b)%n

long long mod_exp(long long a,long long p,long long m)

{

long long exp=a%m, res=1; //

while(p>1)

{

if(p&1)//

res=muti_mod(res,exp,m);

exp = muti_mod(exp,exp,m);

p>>=1;

}

return muti_mod(res,exp,m);

}

//miller-rabin法測試素數, time 測試次數

bool miller_rabin(long long n, long long times)

{

if(n==2)return 1;

if(n<2||!(n&1))return 0;

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

int t=0;

while(u%2==0){

t++;

u/=2;

}

srand(time(0));

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

{

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

x = mod_exp(a, u, n);

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

{

y = muti_mod(x, x, n);

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

return false; //must not

x = y;

}

if( y!=1) return false;

}

return true;

}

long long pollard_rho(long long n,int c)

{//找出一個因子

long long x,y,d,i = 1,k = 2;

srand(time(0));

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

y = x;

while(true) {

i++;

x = (muti_mod(x,x,n) + c) % n;

d = gcd(y-x, n);

if(1 < d && d < n)return d;

if( y == x) return n;

if(i == k) {

y = x;

k <<= 1;

}

}

}

void findFactor(long long n,int k)

{//二分找出所有質因子，存入factor

if(n==1)return;

if(miller_rabin(n, 10))

{

factor[++fac_top] = n;

return;

}

long long p = n;

while(p >= n)

p = pollard_rho(p,k--);//k值變化，防止死循環

findFactor(p,k);

findFactor(n/p,k);

}

int main()

{

long long t,n,min;

cin>>t;

while(t--)

{

cin>>n;

fac_top = min = -1;

if(miller_rabin(n,10))

cout<<"Prime"<<endl;

else

{

findFactor(n,107);

for(int i=0;i<=fac_top;i++){

if(min<0||factor[i]<min)

min = factor[i];}

cout<<min<<endl;

}

}

return 0;

}