1 #include <cstdlib>  2 #include <cctype>  3 #include <cstring>  4 #include <cstdio>  5 #include <cmath>  6 #include <algorithm>  7 #include <vector>  8 #include <string>  9 #include <iostream> 10 #include <map> 11 #include <set> 12 #include <queue> 13 #include <stack> 14 #include <bitset> 15 #include <list> 16 #include <cassert> 17 #include <complex> 18 using namespace std; 19 #define rep(i,a,n) for (int i=a;i<n;i++) 20 #define per(i,a,n) for (int i=n-1;i>=a;i--) 21 #define all(x) (x).begin(),(x).end() 22 //#define fi first 23 #define se second 24 #define SZ(x) ((int)(x).size()) 25 #define TWO(x) (1<<(x)) 26 #define TWOL(x) (1ll<<(x)) 27 #define clr(a) memset(a,0,sizeof(a)) 28 #define POSIN(x,y) (0<=(x)&&(x)<n&&0<=(y)&&(y)<m) 29 typedef vector<int> VI; 30 typedef vector<string> VS; 31 typedef vector<double> VD; 32 typedef long long ll; 33 typedef long double LD; 34 typedef pair<int,int> PII; 35 typedef pair<ll,ll> PLL; 36 typedef vector<ll> VL; 37 typedef vector<PII> VPII; 38 typedef complex<double> CD; 39 const int inf=0x20202020; 40 const ll mod=1000000007; 41 const double eps=1e-9; 42  43 ll powmod(ll a,ll b)             //return (a*b)%mod 44 {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} 45 ll powmod(ll a,ll b,ll mod)     //return (a*b)%mod 46 {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} 47 ll gcd(ll a,ll b)                 //return gcd(a,b) 48 { return b?gcd(b,a%b):a;} 49 // head 50  51 namespace Factor { 52     const int N=1010000; 53     ll C,fac[10010],n,mut,a[1001000]; 54     int T,cnt,i,l,prime[N],p[N],psize,_cnt; 55     ll _e[100],_pr[100]; 56     vector<ll> d; 57  58     inline ll mul(ll a,ll b,ll p) {     //return (a*b)%p 59         if (p<=1000000000) return a*b%p; 60         else if (p<=1000000000000ll) return (((a*(b>>20)%p)<<20)+(a*(b&((1<<20)-1))))%p; 61         else { 62             ll d=(ll)floor(a*(long double)b/p+0.5); 63             ll ret=(a*b-d*p)%p; 64             if (ret<0) ret+=p; 65             return ret; 66         } 67     } 68  69     void prime_table(){     //prime[1..tot]: prime[i]=ith prime 70         int i,j,tot,t1; 71         for (i=1;i<=psize;i++) p[i]=i; 72         for (i=2,tot=0;i<=psize;i++){ 73             if (p[i]==i) prime[++tot]=i; 74             for (j=1;j<=tot && (t1=prime[j]*i)<=psize;j++){ 75                 p[t1]=prime[j]; 76                 if (i%prime[j]==0) break; 77             } 78         } 79     } 80  81     void init(int ps) {                 //initial 82         psize=ps; 83         prime_table(); 84     } 85  86     ll powl(ll a,ll n,ll p) {           //return (a^n)%p 87         ll ans=1; 88         for (;n;n>>=1) { 89             if (n&1) ans=mul(ans,a,p); 90             a=mul(a,a,p); 91         } 92         return ans; 93     } 94  95     bool witness(ll a,ll n) { 96         int t=0; 97         ll u=n-1; 98         for (;~u&1;u>>=1) t++; 99         ll x=powl(a,u,n),_x=0;100         for (;t;t--) {101             _x=mul(x,x,n);102             if (_x==1 && x!=1 && x!=n-1) return 1;103             x=_x;104         }105         return _x!=1;106     }107 108     bool miller(ll n) {109         if (n<2) return 0;110         if (n<=psize) return p[n]==n;111         if (~n&1) return 0;112         for (int j=0;j<=7;j++) if (witness(rand()%(n-1)+1,n)) return 0;113         return 1;114     }115 116     ll gcd(ll a,ll b) {117         ll ret=1;118         while (a!=0) {119             if ((~a&1) && (~b&1)) ret<<=1,a>>=1,b>>=1;120             else if (~a&1) a>>=1; else if (~b&1) b>>=1;121             else {122                 if (a<b) swap(a,b);123                 a-=b;124             }125         }126         return ret*b;127     }128 129     ll rho(ll n) {130         for (;;) {131             ll X=rand()%n,Y,Z,T=1,*lY=a,*lX=lY;132             int tmp=20;133             C=rand()%10+3;134             X=mul(X,X,n)+C;*(lY++)=X;lX++;135             Y=mul(X,X,n)+C;*(lY++)=Y;136             for(;X!=Y;) {137                 ll t=X-Y+n;138                 Z=mul(T,t,n);139                 if(Z==0) return gcd(T,n);140                 tmp--;141                 if (tmp==0) {142                     tmp=20;143                     Z=gcd(Z,n);144                     if (Z!=1 && Z!=n) return Z;145                 }146                 T=Z;147                 Y=*(lY++)=mul(Y,Y,n)+C;148                 Y=*(lY++)=mul(Y,Y,n)+C;149                 X=*(lX++);150             }151         }152     }153 154     void _factor(ll n) {155         for (int i=0;i<cnt;i++) {156             if (n%fac[i]==0) n/=fac[i],fac[cnt++]=fac[i];}157         if (n<=psize) {158             for (;n!=1;n/=p[n]) fac[cnt++]=p[n];159             return;160         }161         if (miller(n)) fac[cnt++]=n;162         else {163             ll x=rho(n);164             _factor(x);_factor(n/x);165         }166     }167 168     void dfs(ll x,int dep) {169         if (dep==_cnt) d.push_back(x);170         else {171             dfs(x,dep+1);172             for (int i=1;i<=_e[dep];i++) dfs(x*=_pr[dep],dep+1);173         }174     }175 176     void norm() {177         sort(fac,fac+cnt);178         _cnt=0;179         rep(i,0,cnt) if (i==0||fac[i]!=fac[i-1]) _pr[_cnt]=fac[i],_e[_cnt++]=1;180             else _e[_cnt-1]++;181     }182 183     vector<ll> getd() {184         d.clear();185         dfs(1,0);186         return d;187     }188 189     vector<ll> factor(ll n) {       //return all factors of n        cnt:the number of factors190         cnt=0;191         _factor(n);192         norm();193         return getd();194     }195 196     vector<PLL> factorG(ll n) {197         cnt=0;198         _factor(n);199         norm();200         vector<PLL> d;201         rep(i,0,_cnt) d.push_back(make_pair(_pr[i],_e[i]));202         return d;203     }204 205     bool is_primitive(ll a,ll p) {206         assert(miller(p));207         vector<PLL> D=factorG(p-1);208         rep(i,0,SZ(D)) if (powmod(a,(p-1)/D[i].first,p)==1) return 0;209         return 1;210     }211 }212 213 /* *************************************************214 * Miller_Rabin算法进行素数测试215 *速度快，可以判断一个  < 2^63的数是不是素数216 *217 **************************************************/218 const int S = 8; //随机算法判定次数，一般8~10就够了219 //计算ret  = (a*b)%c220 long long mult_mod(long long a,long long b,long long  c)221 {222     a %= c;223     b %= c;224     long long ret = 0;225     long long tmp = a;226     while(b)227     {228         if(b & 1)229         {230             ret += tmp;231             if(ret > c)ret -= c;//直接取模慢很多232         }233         tmp <<= 1;234         if(tmp > c)tmp -= c;235         b >>= 1;236     }237     return  ret;238 }239 //计算  ret = (a^n)%mod240 long long pow_mod(long long a,long long n,long long  mod)241 {242     long long ret = 1;243     long long temp = a%mod;244     while(n)245     {246         if(n & 1)ret = mult_mod(ret,temp,mod);247         temp = mult_mod(temp,temp,mod);248         n >>= 1;249     }250     return  ret;251 }252 //通过  a^(n-1)=1(mod n)来判断n是不是素数253 // n-1 = x*2^t中间使用二次判断254 //是合数返回true,不一定是合数返回false255 bool check(long long a,long long n,long long x,long long  t)256 {257     long long ret = pow_mod(a,x,n);258     long long last = ret;259     for(int i = 1; i <= t; i++)260     {261         ret = mult_mod(ret,ret,n);262         if(ret == 1 && last != 1 && last != n-1)return  true;//合数263         last = ret;264     }265     if(ret != 1)return true;266     else return false;267 }268 //**************************************************269 // Miller_Rabin算法270 //是素数返回true,(可能是伪素数)271 //不是素数返回false272 //**************************************************273 bool Miller_Rabin(long long  n)274 {275     if( n < 2)return false;276     if( n == 2)return true;277     if( (n&1) == 0)return false;//偶数278     long long x = n - 1;279     long long t = 0;280     while( (x&1)==0 )281     {282         x >>= 1;283         t++;284     }285     rand();/* *************** */286     for(int i = 0; i < S; i++)287     {288         long long a =  rand()%(n-1) + 1;289         if( check(a,n,x,t) )290             return false;291     }292     return true;293 }294 295 ll x,y,k,n;296 int _;297 int main() {298     Factor::init(200000);299     cin>>_;300     while (_--)301     {302         cin>>n;303         bool ok=Miller_Rabin(n);304         if (n==1)305         {306             cout<<1<<endl;307             continue;308         }309         else if (n==2)310         {311             cout<<"Prime"<<endl;312             continue;313         }314         if (ok) cout<<"Prime"<<endl;315         else316         {317             vector <PLL> p=Factor::factorG(n);318             //for (vector<ll>::iterator i=p.begin();i!=p.end();i++)319              //   cout<<*i<<" ";320              vector<PLL>::iterator i=p.begin();321             //printf("%d\n",*i);322             cout<<i->first<<endl;323         }324     }325 }