rt，TLE on #12

评测记录：https://www.luogu.com.cn/record/72283862

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
inline void read(ll &s){
	s=0; ll f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	s*=f;
}
inline void updmx(ll&x,ll m){if(x<m)x=m;}
inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
inline ll pow(ll a,ll b,ll m){
	ll ans=1; a%=m;
	while(b){if(b&1)ans=(lll)ans*a%m; b>>=1; a=(lll)a*a%m;}
	return ans;
}
inline ll A[10]={2,3,5,7,11,13,17,19,23,29};
inline bool isPrime(ll n){
	if(n==2||n==3)return true;
	if(n%2==0||n==1)return false;
	ll d=n-1; int s=0;
	while(!(d&1))s++,d>>=1;
	for(int i=0;i<10&&A[i]<n;i++){
		ll a=A[i];
		ll x=pow(a,d,n),y=0;
		for(int j=1;j<=s;j++){
			y=(__int128)x*x%n;
			if(y==1&&x!=1&&x!=(n-1))return false;
			x=y;
		}
		if(y!=1)return false;
	}
	return true;
}
inline ll rand_int(ll l,ll r){
	if(l>r)swap(l,r);
	mt19937 rand_num(time(0));
	uniform_int_distribution<ll> dis(l,r);
	return dis(rand_num);
}
inline ll Pollard_Rho(ll n){
	if(n==1)return 1; 
	if(n==4)return 2;
	if(isPrime(n))return n;
	while(1){
		ll c=rand_int(1,n-1);
		auto f=[=](ll x){return ((lll)x*x+c)%n;};
		ll t=0,r=0,p=1,q;
		do{
			for(int i=0;i<128;++i){
				t=f(t),r=f(f(r));
				if(t==r||(q=(lll)p*abs(t-r)%n)==0)break;
				p=q;
			}
			ll d=gcd(p,n);
			if(d>1)return d;
		}while(t!=r);
	}
}
ll T,n;
ll max_fact;
inline void fact(ll x){
	if(x<=max_fact||x<=1)return;
	if(isPrime(x)){updmx(max_fact,x); return;}
	ll p=x;
	while(p>=x)p=Pollard_Rho(x);
	while((x%p)==0)x/=p;
	fact(x); fact(p);
}
int main(){
	read(T);
	while(T--){
		read(n);
		max_fact=0;
		fact(n);
		if(max_fact==n)puts("Prime");
		else printf("%lld\n",max_fact);
	}
	return 0;
}