rt，代码：

#include<bits/stdc++.h>
#define int __int128_t
using namespace std;
const int pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37},prsiz=12;
uint64_t n,t,ans,seed=19260817,sd;
int gen(){
	seed^=seed<<13,seed^=seed>>17,seed^=seed<<5;
	return seed;
}
int qpow(int x,int y,int mod){
	int ret=1;
	x%=mod;
	while(y){
		if(y&1)
			ret=ret*x%mod;
		x=x*x%mod,y>>=1;
	}
	return ret;
}
bool check(int x,int p){
	int d=p-1,val=qpow(x,d,p);
	if(val!=1)
		return 1;
	while(!(d&1)){
		d>>=1,val=qpow(x,d,p);
		if(val==p-1)
			return 0;
		else if(val!=1)
			return 1;
	}
	return 0;
}
bool miller_rabin(int p){
	if(p>40){
		for(int i=1;i<=prsiz;i++)
			if(check(pri[i],p))
				return 0;
		return 1;
	}
	for(int i=1;i<=prsiz;i++)
		if(p==pri[i])
			return 1;
	return 0;
}
int f(int x,int mod){
	return (qpow(x,x,mod)+sd)%mod;
}
int floyd(int x,int st){
	sd=gen()%x;
	int fst,slw,ret=1,g;
	fst=slw=gen()%x,fst=f(fst,x);
	for(int i=0;fst!=slw;i++){
		ret=ret*(fst-slw+x)%x;
		if(!ret)
			ret=fst-slw+x;
		if(!(i%st)){
			g=__gcd(ret,x);
			if(g!=1)
				return g;
			ret=1;
		}
		fst=f(f(fst,x),x),slw=f(slw,x);
	}
	return __gcd(ret,x);
}
int pollard_rho(int x){
	if(x==1)
		return 1;
	if(miller_rabin(x))
		return x;
	int k=1,st=int(log((uint64_t)x))<<1|1;
	while(k==1)
		k=floyd(x,st);
	return max(pollard_rho(k),pollard_rho(x/k));
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n,ans=pollard_rho(n);
		if(ans==n)
			cout<<"Prime\n";
		else
			cout<<ans<<'\n';
	}
	return 0;
}

除了#12全T