输入

1
8897

可以运行出正确结果

输入

4
2
13
134
8897

死循环

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath> 
#define ll long long 
using namespace std;
ll test[12]={2,3,5,7,11,13,17,19,23,29,31,37},rag=12;
ll ans;
ll mul(ll x,ll y,ll m){
	return (__int128)x*y%m;
}
ll qpow(ll b,ll p,ll m){
	ll res=1,b1=b;
	while(p){
		if(p&1) res=mul(res,b1,m);
		b1=mul(b1,b1,m);
		p=p>>1; 
	}
	return res;
}
bool check(ll a,ll p){
	ll d=p-1,get=qpow(a,d,p);
	if(get!=1) return true;
	while((d&1)^1){
		d=d>>1; get=qpow(a,d,p);
		if(get==p-1) return false;
		else if(get!=1) return true; 
	}
	return false;
}
bool prime(ll x){
	if(x>test[rag-1]){
		for(int i=0;i<rag;i++){
			if(check(test[i],x)) return false; 
		} 
		return true;
	}
	else{
		for (int i=0;i<rag;i++){
			if(x==test[i]) return true; 
		}
		return false;
	}
}
ll f(ll x,ll c,ll m){
	return (mul(x,x,m)+c)%m;
}
ll gcd(ll a,ll b){
	if(b==0) return a;
	return gcd(b,a%b);
}
ll rho(ll x){
	ll s=0,t=0,c=rand()%(x-1)+1,val,d;
	int goal,stp;
	for (goal=1;;goal=goal<<1,s=t,val=1){
		for (stp=1;stp<=goal;stp++){
			t=f(t,c,x);
			val=mul(val,abs(s-t),x);
			if((stp%127)==0){
				d=gcd(val,x);
				if(d>1&&d!=x) return d; 
			}
		}
		d=gcd(val,x);
		if(d>1&&d!=x) return d;
	}
}
void solve(ll x){
	if(x<=ans||x<2) return;
	if(prime(x)){
		ans=x; return;
	}
	ll p=rho(x);
	while(p>=x){
		p=rho(x);
	} 
	while(x%p==0){
		x=x/p;
	}
	solve(x); solve(p);
}
int main(){
	int T; ll n;
	scanf("%d",&T);
	while(T--){
		scanf("%lld",&n);
		if(prime(n)){
			printf("Prime\n");
		} 
		else{
			ans=1;
			solve(n);
			printf("%lld\n",ans);
		}
	}
	return 0;
}