ACM模板之数论（不断更新ing）

 1 //1：基本素数判定算法
 2 //判断n是否为素数，只需要将i从2枚举到sqrt(n)。
 3 //理论支持： 若n是合数,则必然可以分解成两数之积,而
 4 //             这两个数不可能同时大于sqrt(n),则n必有
 5 //           一个小于等于sqrt(n)的约数。
 6 bool isPrime_fundamental( int n )
 7 {
 8     int r = sqrt(n) + 1e-6;                            
 9     for ( int i = 2; i <= r; i++ )                    /*这样最快，1e-6避免误差
10     //for ( int i = 2; i <= sqrt(n) + 1e-6; i++ )    /*由于每次sqrt(n)都会计算，所以比较慢*/
11     //for ( int i = 2; i * i <= n; i++ )            /*由于每次都会计算i*i，所以最慢*/
12     {
13         if ( n % i == 0 ) return false;
14     }
15     return true;
16 }
17 
18 //2：米勒拉宾测试算法
19 //快速幂求a^b%mod
20 int pow_mod( int a, int b, int mod )
21 {
22     int ans = 1, w = a % mod;
23     while ( b )
24     {
25         if ( b & 1 )
26         {
27             ans = ( long long ) ans * w % mod;
28         }
29         b = b >> 1;
30         w = ( long long ) w * w % mod;
31     }
32     return ans;
33 }
34 
35 //米勒拉宾大法
36 bool mr( int n, int a )
37 {
38     if ( n % a == 0 ) return false;
39     int r = 0, s = n - 1;
40     while ( ( s & 1 ) == 0 )
41     {
42         s = s >> 1;
43         r++;
44     }
45     int k = pow_mod( a, s, n );
46     if ( k == 1 ) return true;
47     for ( int j = 0; j < r; j++, k = ( long long ) k * k % n )
48     {
49         if ( k == n - 1 ) return true;    //I don‘t understand!
50     }
51     return false;
52 }
53 
54 //判断素数
55 bool isPrime( int n )
56 {
57     if ( n == 2 || n == 3 || n == 5 || n == 7 ) return true;
58     if ( n & 1 == 0 ) return false;
59     int tab[] = { 2, 3, 5, 7 };
60     for ( int i = 0; i < 4; i++ )
61     {
62         if ( !mr( n, tab[i] ) ) return false;
63     }
64     return true;
65 }