数据范围很大，用米勒罗宾测试和Pollard_Rho法可以分解大数。
模板在代码中 O.O
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std; __int64 pri[]= {,,,,,,,,,,};//用小素数表做随机种子避免第一类卡米歇尔数的误判
__int64 multi(__int64 a,__int64 b,__int64 n) //乘法快速幂
{
__int64 tmp=;
while(b)
{
if(b&)
{
tmp+=a;
if(tmp>=n) tmp-=n;
}
a<<=;
if(a>=n) a-=n;
b>>=;
}
return tmp;
}
__int64 multimod(__int64 a,__int64 m,__int64 n) //乘法快速幂
{
__int64 tmp=;
a%=n;
while(m)
{
if(m&) tmp=multi(tmp,a,n);
a=multi(a,a,n);
m>>=;
}
return tmp;
}
__int64 gcd(__int64 a, __int64 b) //迭代算法
{
while(b)
{
__int64 c=a%b;
a=b;
b=c;
}
return a;
}
bool Miller_Rabin(__int64 n) //大素数判断
{
if(n<)
return false;
if(n==)
return true;
if(!(n&))
return false;
__int64 k=,j,m,a;
m=n-;
while(!(m&))
{
m>>=;
k++;
}
for(int i=; i<; i++)
{
if(pri[i]>=n)
return true;
a=multimod(pri[i],m,n);
if(a==)
continue;
for(j=; j<k; j++)
{
if(a==n-)
break;
a=multi(a,a,n);
}
if(j==k)
return false;
}
return true;
}
__int64 pollard_rho(__int64 c,__int64 n) //查找因数
{
__int64 i,x,y,k,d;
i=;
x=y=rand()%n;
k=;
do
{
i++;
d=gcd(n+y-x,n);
if(d> && d<n)
return d;
if(i==k)
{
y=x;
k<<=;
}
x=(multi(x,x,n)+n-c)%n;
}
while(y!=x);
return n;
}
__int64 rho(__int64 n)
{
if(Miller_Rabin(n))
return n;
__int64 t=n;
while(t>=n)
t=pollard_rho(rand()%(n-)+,n);
__int64 a=rho(t);
__int64 b=rho(n/t);
return a<b? a:b;
} __int64 ans[],flag;
void rhoAll(__int64 n) //计算全部质因子
{
if(Miller_Rabin(n))
{
ans[flag++]=n;
return;
}
__int64 t=n;
while(t>=n)
t=pollard_rho(rand()%(n-)+,n);
rhoAll(t);
rhoAll(n/t);
return;
}
int main()
{
//freopen("in.txt","r",stdin);
int t;
__int64 n;
scanf("%d",&t);
while(t--)
{
flag=;
scanf("%I64d",&n);
if(Miller_Rabin(n))
printf("Prime\n");
else
{
//rhoAll(n);
printf("%I64d\n",rho(n));
}
/*for(int i=0;i<flag;i++) //输出全部质因子
if(i!=flag-1)
printf("%I64d ",ans[i]);
else
printf("%I64d\n",ans[i]);*/
}
return ;
}