虽然很久以前就听说过PR算法，但前几天第一次打。

首先miller rabin判断素数，不在复杂度瓶颈。

pollard rho倍增环长，复杂度是\(O(n^{\frac{1}{4}} log n)\)的。

然而这样复杂度较高，比较难过加强后的数据。

可以考虑每次倍增时把乘积存下来，然后在增加环长时一次gcd，这样应该是\(O(n^{\frac{1}{4}})\)

#pragma GCC optimize(3)#pragma GCC optimize("Ofast")#pragma GCC optimize("inline")#include 
    
     using namespace std;typedef long long i64;typedef unsigned long long u64;typedef vector
     
       vi64;i64 fast_pow(i64 x,i64 y,i64 z){    //cerr<<"fp"<
      
       <<" "<
       
        <<" "<
        
         <
         
          >=1,x=(__int128)x*x%z) if (y&1) ret=(__int128)ret*x%z; return ret;}u64 RAND(){ return ((u64)rand()*rand()+rand());}const int sp[]={2,3,5,7,11,13,17,19,23,29,31,37,43,47};bool is_prime(i64 n){ //cerr<<"is_prime"<
          
           <
           
            >=1; ++b; } for (int i=0; i<12&&sp[i]
            
             >=__builtin_ctzll(b); while (a){ a>>=__builtin_ctzll(a); if (a
             
              1) return tmp; g=(__int128)fix(x-y,n)*g%n; if (i==k){ g=gcd(g,n); if (g>1){ if (g==n){ x=y; while (g==1){ x=((__int128)x*x+c)%n; g=gcd(fix(x-y,n),n); } } return g; } y=x; k<<=1; } }}vi64 v;void fj(i64 n){ if (n==1) return; if (is_prime(n)){ //cerr<<"N"<
              
               <
               
                =n){ p=pollard_rho(n,RAND()%n); } fj(p); fj(n/p);}typedef vector
                
                 
                   > vpi64i;vpi64i vv;int k,p;int fp(int x,int y){ int ret=1; for (; y; y>>=1,x=(i64)x*x%p) if (y&1) ret=(i64)ret*x%p; return ret;}int C(int x){ return ((u64)x*(x+1)>>1)%p;}int mul(int x,int y){ return (i64)x*y%p;}int add(int x,int y){ return (x+=y)>=p?x-p:x;}int main(){ int t; cin>>t; while (t--){ i64 n; cin>>n; //FastDiv fd(p); if (n==1){ cout<<1<<'\n'; continue; } v.clear(); fj(n); sort(v.begin(),v.end()); (v.back()==n?cout<<"Prime":cout<
                  
                   <<'\n'; }}