zoj 月赛B题（快速判断一个大数是否为素数）
时间：2014-03-05 17:36:58
收藏：0
阅读：455
给出一个64位的大数，如何快速判断其是否为素数
|
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
93
94
95
96
97
98
99
100
101
102
103
104
105 |
#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>using
namespace std;typedef
long long LL;LL n,m;//****************************************************************// Miller_Rabin 算法进行素数测试//速度快，而且可以判断 <2^63的数//****************************************************************const
int S=20;//随机算法判定次数，S越大，判错概率越小LL mult_mod(LL a,LL b,LL mod) //(a*b)%c a,b,c<2^63{ a%=mod; b%=mod; LL ans=0; while(b) { if(b&1) { ans=ans+a; if(ans>=mod) ans=ans-mod; } a=a<<1; if(a>=mod) a=a-mod; b=b>>1; } return
ans;}LL pow_mod(LL a,LL b,LL mod) // a^b%mod{ LL ans=1; a=a%mod; while(b) { if(b&1) { ans=mult_mod(ans,a,mod); } a=mult_mod(a,a,mod); b=b>>1; } return
ans;}//以a为基,n-1=x*2^t a^(n-1)=1(mod n) 验证n是不是合数//一定是合数返回true,不一定返回falsebool
check(LL a,LL n,LL x,LL t){ LL ret=pow_mod(a,x,n); LL last=ret; for(int
i=1;i<=t;i++) { ret=mult_mod(ret,ret,n); if(ret==1 && last!=1 && last!=n-1) return
true;//合数 last=ret; } if(ret!=1) return
true; else
return false;}// Miller_Rabin()算法素数判定//是素数返回true.(可能是伪素数，但概率极小)//合数返回false;bool
Miller_Rabin(long
long n){ if(n<2)return
false; if(n==2) return
true; if( (n&1)==0) return
false;//偶数 LL x=n-1; LL t=0; while( (x&1)==0 ) { x>>=1;t++;} for(int
i=0;i<S;i++) { LL a=rand()%(n-1)+1;//rand()需要stdlib.h头文件 if(check(a,n,x,t)) return
false;//合数 } return
true;}int
main(){ // n,m; while(scanf("%lld%lld",&n,&m)>0) { LL sum=0; for(LL i=0; i<m; i++) { sum+=(LL)(pow((double)(n),i)+0.5); } //printf("%lld\n",sum); if(Miller_Rabin(sum)) printf("YES\n"); else printf("NO\n"); } return
0;} |
zoj 月赛B题（快速判断一个大数是否为素数）,布布扣,bubuko.com
原文：http://www.cnblogs.com/ziyi--caolu/p/3581345.html
评论（0）