题意：给出一个N，若N为素数，输出Prime。若为合数，输出最小的素因子。
思路：Pollard rho大整数分解，模板题
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cstdlib>
#include <cmath> using namespace std;
long long n;
long long minf;
long long multi(long long a,long long b,long long mod){
a=a%n;
long long ret=;
while(b){
if(b&){
//ret=(ret+a)%mod;
ret=ret+a;
if(ret>=mod)
ret-=mod; //原来用取模1500ms，现在547ms。速度变为原来的1/3，没想到取模那么慢。。。
}
a=a<<;
if(a>=mod)
a-=mod;
//a=(a+a)%mod;
b=b>>;
}
return ret;
}
long long quickPow(long long a,long long b,long long mod) {
long long ret=;
while(b) {
if(b&)
ret=multi(ret,a,mod);
a=multi(a,a,mod);
b=b>>;
}
return ret;
} bool witness(long long a,long long n) {
long long m=n-;
int j=;
while(!(m&)) {
j++;
m=m>>;
}
long long x=quickPow(a,m,n);
if(x==||x==n-)
return false;
while(j--) {
x=(x*x)%n;
if(x==n-)
return false;
}
return true;
}
//用这个547ms
bool Miller_Rabin(long long n) {
if(n<)
return false;
if(n==)
return true;
if(!(n&))
return false;
long long m=n-;
int j=;
while(!(m&)) {
j++;
m=m>>;
}
for(int i=; i<=; i++) {
long long a=rand()%(n-)+;
long long x=quickPow(a,m,n);
if(x==||x==n-)
continue; //n可能为素数
int k=j;
bool flag=false;
while(k--) {
x=(x*x)%n;
if(x==n-){
flag=true; //n可能为素数
break;
}
}
if(flag)
continue;
return false; //n为合数
}
return true;
}
//用这个454ms
bool Miller_Rabin2(long long n)
{
if(n==)return ;
if(n<||!(n&))return ; long long a, u=n-, x, y;
int t=;
while(u%==){
t++;
u/=;
}
srand();
for(int i=;i<;i++)
{
a = rand() % (n-) + ;
x = quickPow(a, u, n);
for(int j=;j<t;j++)
{
y = multi(x,x,n);
//如果n是素数那么x^2mod n = 1,仅有两个根（不同余），+1和-1(n-1)。如果当x^2 mod n=1，但是x不为1或n-1，那么n是合数
if ( y == && x != && x != n- )
return false; //为合数
x = y;
}
if( y!=) return false;//最后y的值为a^(n-1)。由费马小定理 a^(n-1) mod n 恒等于 1 则可以认为 n 是素数。若有不为1的情况，则n为合数
}
return true;
} long long gcd(long long a,long long b) {
return b==?a:gcd(b,a%b);
}
long long pollard_rho(long long n,long long c) {
long long x,y,d,i=,k=;
x=rand()%(n-)+;
y=x;
while() {
i++;
x=(multi(x,x,n)+c)%n;
d=gcd(y-x,n);
if(<d && d<n)
return d;
if(y==x)
return n;
if(i==k) {
y=x;
k=k<<;
}
}
}
//对n进行素数分解
void factorFind(long long n,int k) {
if(n==)
return;
if(Miller_Rabin(n)) {
if(n<minf)
minf=n;
return;
}
long long p=n;
while(p>=n)
p=pollard_rho(p,k--);
factorFind(p,k);
factorFind(n/p,k);
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%I64d",&n);
minf=n+;
if(Miller_Rabin(n))
printf("Prime\n");
else {
factorFind(n,);
printf("%I64d\n",minf);
}
}
return ;
}