POJ1811
给一个大数，判断是否是素数，如果不是素数，打印出它的最小质因数
随机素数测试（Miller_Rabin算法）
求整数素因子（Pollard_rho算法）
科技题
#include<cstdlib>
#include<cstdio>
const int maxn=;
const int S=;
int tot;
long long n;
long long factor[maxn];
long long muti_mod(long long a,long long b,long long c)
{
//(a*b) mod c a,b,c<2^63
a%=c;
b%=c;
long long ret=;
while(b)
{
if(b&)
{
ret+=a;
if(ret>=c) ret-=c;
}
a<<=;
if(a>=c) a-=c;
b>>=;
}
return ret;
}
long long pow_mod(long long x,long long n,long long mod)
{
//x^n mod c
if(n==) return x%mod;
int bit[],k=;
while(n)
{
bit[k++]=n&;
n>>=;
}
long long ret=;
for(k=k-;k>=;k--)
{
ret=muti_mod(ret,ret,mod);
if(bit[k]==) ret=muti_mod(ret,x,mod);
}
return ret;
}
bool check(long long a,long long n,long long x,long long t)
{
long long ret=pow_mod(a,x,n),last=ret;
for(int i=;i<=t;i++)
{
ret=muti_mod(ret,ret,n);
if(ret==&&last!=&&last!=n-) return ;
last=ret;
}
if(ret!=) return ;
return ;
}
bool Miller_Rabin(long long n)
{
long long x=n-,t=;
while((x&)==) x>>=,t++;
bool flag=;
if(t>=&&(x&)==)
{
for(int k=;k<S;k++)
{
long long a=rand()%(n-)+;
if(check(a,n,x,t)) {flag=;break;}
flag=;
}
}
if(flag==||n==) return ;
return ;
}
long long gcd(long long a,long long b)
{
if(a==) return ;
if(a<) return gcd(-a,b);
while(b)
{
long long t=a%b;a=b;b=t;
}
return a;
}
long long Pollard_rho(long long x,long long c)
{
long long i=,x0=rand()%x,y=x0,k=;
while()
{
i++;
x0=(muti_mod(x0,x0,x)+c)%x;
long long d=gcd(y-x0,x);
if(d!=&&d!=x) return d;
if(y==x0) return x;
if(i==k)
{
y=x0;
k+=k;
}
}
}
void findfac(long long n) //递归分解质因数
{
if(!Miller_Rabin(n))
{
factor[tot++]=n;
return;
}
long long p=n;
while(p>=n) p=Pollard_rho(p,rand()%(n-)+);
findfac(p);
findfac(n/p);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%I64d",&n);
if(!Miller_Rabin(n))
{
printf("Prime\n");
continue;
}
tot=;
findfac(n);
long long ans=factor[];
for(int i=;i<tot;i++)
if(factor[i]<ans) ans=factor[i];
printf("%I64d\n",ans);
}
return ;
}