Miller Rabin算法

1. #include <iostream> 
3. using namespace std; 
5. typedef unsigned __int64 llong; 
7. llong mod_pro(llong x,llong y,llong n) 
8. { 
9.     llong ret=0,tmp=x%n; 
10.     while(y) 
11.     { 
12.         if(y&0x1)if((ret+=tmp)>n)ret-=n; 
13.         if((tmp<<=1)>n)tmp-=n; 
14.         y>>=1; 
15.     } 
16.     return ret; 
17. } 
18. llong mod(llong a,llong b,llong c) 
19. { 
20.     llong ret=1; 
21.     while(b) 
22.     { 
23.         if(b&0x1)ret=mod_pro(ret,a,c); 
24.         a=mod_pro(a,a,c); 
25.         b>>=1; 
26.     } 
27.     return ret; 
28. } 
29. llong ran() 
30. { 
31.     llong ret=rand(); 
32.     return ret*rand(); 
33. } 
34. bool is_prime(llong n,int t) 
35. { 
36.     if(n<2)return false; 
37.     if(n==2)return true; 
38.     if(!(n&0x1))return false; 
39.     llong k=0,m,a,i; 
40.     for(m=n-1;!(m&1);m>>=1,k++); 
41.     while(t--) 
42.     { 
43.         a=mod(ran()%(n-2)+2,m,n); 
44.         if(a!=1) 
45.         { 
46.             for(i=0;i<k&&a!=n-1;i++) 
47.                 a=mod_pro(a,a,n); 
48.             
49.             if(i>=k)return false; 
50.         } 
51.     } 
52.     return true; 
53. } 
54. int main() 
55. { 
56.     llong n; 
57.     while(scanf("%I64u",&n)!=EOF) 
58.         if(is_prime(n,3)) 
59.             cout<<"YES\n"; 
60.         else 
61.             cout<<"NO\n"; 
62.         return 0; 
63. }

Miller Rabin算法

原文：http://www.cnblogs.com/towardsSun/p/4070223.html