很好的入门题
先测试是否为素数，若不是则进行素因子分解，算法详见总结贴 miller robin 和pollard rho算法
AC代码
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
long long ans;
long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}
long long random(long long n)
{
return (long long)(rand()%(n-)+);
}
long long multi(long long a,long long b,long long m)//a*b%m
{
long long res=;
while(b>)
{
if(b&)
res=(res+a)%m;
b>>=;
a=(a<<)%m;
}
return res;
}
long long quickmod(long long a,long long b,long long m) //a^b%m
{
long long res=;
while(b>)
{
if(b&)
res=multi(res,a,m);
b>>=;
a=multi(a,a,m);
}
return res;
}
int check(long long a,long long n,long long x,long long t)
{
long long res=quickmod(a,x,n);
long long last=res;
for(int i=;i<=t;i++)
{
res=multi(res,res,n);
if(res==&&last!=&&last!=n-) return ;
last=res;
}
if(res!=) return ;
return ;
} int primetest(long long n)
{
if(n<)return ;
if(n==)return ;
if((n&)==) return ;
long long x=n-;
long long t=;
while((x&)==){x>>=;t++;}
for(int i=;i<;i++)
{
long long a=random(n);
if(check(a,n,x,t))
return ;
}
return ;
} long long pollardrho(long long n,long long c)
{
long long x,y,d,i,k;
i=;k=;
x=random(n);
y=x;
while()
{
i++;
x=(multi(x,x,n)+c)%n;
long long tmp=y-x>=?y-x:x-y;
d=gcd(tmp,n);
if(d>&&d<n)
return d;
if(y==x)
return n;
if(i==k)
{
y=x;
k+=k;
}
}
}
void findfac(long long n)
{
if(n==)
return;
if(primetest(n))
{
ans=min(ans,n);
return;
}
long long p=n;
while(p>=n)
p=pollardrho(n,random(n-));
findfac(p);
findfac(n/p);
}
int main()
{
int t;
long long n;
scanf("%d",&t);
while(t--)
{
scanf("%I64d",&n);
if(primetest(n))
{
puts("Prime");
continue;
}
ans=n;
findfac(n);
printf("%I64d\n",ans);
}
return ;
}