传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3667
思路：首先我们说说Miller_Rabin算法
我们发现了费马小定理
那它倒过来对不对呢
如果a^(p-1)=1(mod p),那么p一定是素数吗？
很不幸，是错的
虽然出错概率很低，但是可以被卡
于是我们就给它打补丁
我们又找到了一个二次探测的方法
如果p是质数，那么x^2=1(mod p)只有两个解1,p-1 (-1)
那么它倒过来对不对呢
很不幸，又是错的
但是两个错误算法加到一起，出错概率就很低了
那么我们先随机出一些数a[i]
每次拿出一个数a
先用费马小定理去测试
那么我们就要算a^(n-1)%n
把n-1拆成2^s*d的形式
这样我们就可以顺便进行二次探测了
先算出a^d次方
然后平方s次不就是a^(n-1)吗
平方的时候顺便检查一下
最后再用费马小定理检测即可
可以证明一次检测出错的概率是1/4
那么很多次后就几乎不出错了
然后就是pollard_rho了
设要分解的数是n
如果我们有两个随机数x，y
如果gcd(x-y,n)!=1&&gcd(x-y,n)!=n
那么p=gcd(x-y,n)是n的一个约数
随机根号n次（1，n）的数，就有很大概率有同样的数
那么随机根号p次，就很有可能有两个数的差是p的倍数了
这样我们就会走到一个环上，最后就相遇了、
实现时设计一个随机函数f(x)
设定k为此次暴力跳的路径长
每次倍长
x暴力迭代
每次做差求gcd
达到k次后把y赋为x
形象一点就是两个指针在rho型的东西上走
走到环上相同的点，就可以得到一个p的倍数，p是n的一个因子
然后把这个数和n求gcd，就有可能得到一个约数
先特判n是否为质数
然后因为有可能直接走到n的环，所以如果分解不出n之外的因子那就说明这个随机函数会使你直接走到n的环上，所以再换一个重试即可
拆出一个因数d后递归处理d和n/d即可
还有一点就是快速乘法，这题的模数是longlong的，但是又不想写高精度
一种处理是把乘法看做多次加法，类似快速幂去做
高端的O（1）做法是：
然后就可以解决这道模板题了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define abs(a) (a>0?a:-(a))
typedef long long ll;
const ll a[]={2,3,5,7,11,13,17,19,23,29};
using namespace std;
int cas;ll maxs;
void read(ll &x){
char ch;
for (ch=getchar();!isdigit(ch);ch=getchar());
for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll mul(ll a,ll b,ll p){
ll d=((long double)a/p*b+1e-8);
ll res=a*b-d*p;
res=res<0?res+p:res;
return res;
}
ll qpow(ll a,ll b,ll c){
ll res=1;
for (;b;b>>=1,a=mul(a,a,c))
if (b&1) res=mul(res,a,c);
return res;
}
bool check(ll a,ll n,ll r,ll s){
ll x=qpow(a,r,n),pre=x;
for (int i=1;i<=s;i++){
x=mul(x,x,n);
if (x==1&&pre!=1&&pre!=n-1) return 0;
pre=x;
}
if (x!=1) return 0;
return 1;
}
bool MR(ll n){
if (n<=1) return 0;
ll r=n-1,s=0;
while (!(r&1)) r>>=1,s++;
for (int i=0;i<9;i++){
if (a[i]==n) return 1;
if (!check(a[i],n,r,s)) return 0;
}
return 1;
}
ll pol_rho(ll n,ll c){
//printf("%lld %lld
",n,c);
ll k=2,x=rand()%n,y=x,p=1;
for (ll i=1;p==1;i++){
x=(mul(x,x,n)+c)%n;
p=y>x?y-x:x-y;
p=gcd(n,p);
if (i==k) y=x,k+=k;
//cout<<" "<<x<<' '<<y<<endl;
}
return p;
}
void solve(ll n){
//printf("%lld
",n);
if (n==1) return;
if (MR(n)){maxs=max(maxs,n);return;}
ll t=n;
while (t==n) t=pol_rho(n,rand()%(n-1));
//printf("t=%lld
",t);
solve(t),solve(n/t);
}
int main(){
srand(1564651598);
/*ll a,b,c;
scanf("%lld %lld %lld",&a,&b,&c);
printf("%lld
",mul(a,b,c));*/
//for (int i=1;i<=1000;i++) if (MR(i)) printf("%d ",i);puts("");
scanf("%d",&cas);
while (cas--){
ll x;maxs=0;
read(x),solve(x);
if (maxs==x) puts("Prime");
else printf("%lld
",maxs);
}
return 0;
}