poj1811-模板题。大数分解+大质数测试（费马+rho）

Description

Input

Output

Sample Input

2
5
10

Sample Output

Prime
2

Source

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define LL __int64
const LL Max = (LL) 1 << 62;
LL p[10]={2,3,5,7,11,13,17,19,23,29};
LL gcd(LL a,LL b){
	return b?gcd(b,a%b):a;
}
//计算a*b%n
inline LL multi_mod(LL a,LL b,LL mod)
{
    LL sum=0;
    while(b)
    {
        if(b&1)    sum = (sum + a) % mod;
        a <<= 1;
        b >>= 1;
        if (a >= mod) a %= mod;
    }
    return sum;
}


 //a^b%m
LL qpow(LL a,LL m){
	LL ans=1;
	while(b){
		if(b&1) ans = multi_mod(ans,a,m);
        a = multi_mod(a,m);
        b >>= 1;
		
	}
	return ans;
}

LL pollard(LL n )
{
    LL x,y,c=0,d,i=1,k=2;
    while(c==0 || c==2 ) c = abs( rand())%(n-1) + 1;
    x = y = (rand( )%( n-1 )) + 1;
   do
    {
      i++;
	  d = gcd( y + n - x,n );
       if( d >1 && d < n )
           return d; 
       if( i == k )
       {
          y = x; k <<= 1;        
       }    
       x = (multi_mod( x,x,n )+n-c )%n;
     }while( x != y );
     return n; 
 }

 
 

bool MillerRabinTest(LL x,LL n){
	LL y=n-1;
	while(!(y&1)) y>>=1;
	x=qpow(x,n);
	while(y<n-1&&x!=1&&x!=n-1)
		x=(x*x)%n,y<<=(LL)1;
	return x==n-1||y&1==1;
}

bool isPrime32(LL n){
	if(n==2||n==7||n==61) return 1;
	if(n==1||(n&1)==0) return 0;
	return MillerRabinTest(2,n)&&MillerRabinTest(7,n)&&MillerRabinTest(61,n);
}
 LL pollard_min(LL n)
{
    LL p,b=Max;
    if(n==1)    return Max;
    if(isPrime32(n))    return n;
    p = pollard(n);
    a = pollard_min(p);//二分查找
    b = pollard_min(n / p);
    return a < b ? a : b;
}
int main(){
	int T;
	LL N;
	scanf("%d",&T);
	while(T--){
		scanf("%I64d",&N);
		if(isPrime32(N))
		printf("Primen");
		else
		  printf("%I64dn",pollard_min(N));
		
		
	}
	
}