题解
算导上面有讲解。
用MillerRabin和PollardRho合力解决。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
using namespace std;
typedef long long ll;
int T;
ll prime[]={2,3,5,7,11,13,17,19,23,61};
ll gcd(ll a,ll b){
return (!b)?a:gcd(b,a%b);
}
ll mul(ll a,ll b,ll c){
ll res=0;
while(b){
if(b&1)res=(res+a)%c;
a=(a+a)%c,b>>=1;
}
return res;
}
ll Pow(ll a,ll b,ll c){
ll res=1;
a%=c;
while(b){
if(b&1)res=mul(res,a,c);
a=mul(a,a,c),b>>=1;
}
return res;
}
bool witness(ll a,ll n,ll d,ll r){
ll t=Pow(a,d,n),_t=t;
for(ll i=1;i<=r;i++){
t=mul(t,t,n);
if(t==1&&_t!=1&&_t!=n-1)
return 1;
_t=t;//基于二次探测定理的操作
}
if(t!=1)return 1;//基于费马小定理的操作
return 0;
}
bool Miller_Rabin(ll n){//1:质数
if(n==2)return 1;
if(n<=1||n%2==0)return 0;
for(int i=0;i<10;i++)
if(n==prime[i])return 1;
ll R=n-1,S=0;
for(;R%2==0;R>>=1,S++);//n-1=d*2^r
for(int i=0;i<10;i++)//10:测试次数
if(witness(prime[i],n,R,S))
return 0;
return 1;
}
//根据算导，c最好不要是0或者2...
//为什么呢？
ll Pollard_Rho(ll n,ll c){
ll x=Pow(rand(),rand(),n),y=x,k=2,d=1,t;
for(ll i=1;d==1;i++){
x=(mul(x,x,n)+c)%n;
if(x-y<0)t=y-x;
else t=x-y;
d=gcd(t,n);
if(i==k)y=x,k<<=1;
}
return d;
}
ll dfs(ll n){
if(n==1)return 1;
if(Miller_Rabin(n))return n;
ll fac=n,Lans,Rans;
while(fac==n)
fac=Pollard_Rho(n,rand()%(n-1)+1);
Lans=dfs(fac),Rans=dfs(n/fac);
return min(Lans,Rans);
}
void init(){
scanf("%d",&T);
srand('z'+'q'+'y'+'1'+'0'+'1'+'8'+1);
}
void solve(){
while(T--){
ll N;
scanf("%lld",&N);
ll ans=dfs(N);
if(ans==N)printf("Prime\n");
else printf("%lld\n",ans);
}
}
int main(){
init();
solve();
return 0;
}