首先是最经典的素数判定问题,先贴上基本的素数判定算法和米勒拉宾测试算法。
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 }
常用的模板集合:
1 //update date: 2015.7.27 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 using namespace std; 8 9 typedef long long ll; 10 const int N = 10000001; 11 const int M = 1000001; 12 bool visit[N]; 13 int prime[M]; 14 int pn; 15 16 void sieve( int n ) 17 { 18 int r = sqrt( n + 0.5 ); 19 memset( visit, 0, sizeof(visit) ); 20 visit[0] = visit[1] = 1; 21 for ( int i = 2; i <= r; i++ ) 22 { 23 if ( !visit[i] ) 24 { 25 for ( int j = i * i; j <= n; j += i ) 26 { 27 visit[j] = 1; 28 } 29 } 30 } 31 } 32 33 void get_prime( int n ) 34 { 35 sieve(n); 36 pn = 0; 37 for ( int i = 0; i <= n; i++ ) 38 { 39 if ( !visit[i] ) 40 { 41 prime[pn++] = i; 42 } 43 } 44 } 45 46 void better_get_prime() 47 { 48 pn = 0; 49 memset( visit, 0, sizeof(visit) ); 50 visit[0] = visit[1] = 1; 51 for ( int i = 2; i < N; i++ ) 52 { 53 if ( !visit[i] ) prime[pn++] = i; 54 for ( int j = 0; j < pn && ( ll ) i * prime[j] < N; j++ ) 55 { 56 visit[i * prime[j]] = 1; 57 if ( i % prime[j] == 0 ) break; 58 } 59 } 60 } 61 62 ll gcd( ll a, ll b ) 63 { 64 return b ? gcd( b, a % b ) : a; 65 } 66 67 ll extgcd( ll a, ll b, ll &d, ll &x, ll &y ) 68 { 69 if ( !b ) 70 { 71 d = a, x = 1, y = 0; 72 } 73 else 74 { 75 extgcd( b, a % b, d, y, x ); 76 y -= x * ( a / b ); 77 } 78 } 79 80 ll inv( ll a, ll mod ) 81 { 82 ll d, x, y; 83 extgcd( a, mod, d, x, y ); 84 return d == 1 ? ( x + mod ) % mod : -1; 85 } 86 87 ll pow_mod( ll a, ll n, ll mod ) 88 { 89 ll ans = 1, w = a % mod; 90 while ( n ) 91 { 92 if ( n & 1 ) 93 { 94 ans = ans * w % mod; 95 } 96 w = w * w % mod; 97 n >>= 1; 98 } 99 return ans; 100 } 101 102 int euler_phi( int n ) 103 { 104 int ans = n; 105 for ( int i = 2; i * i <= n; i++ ) 106 { 107 if ( n % i == 0 ) 108 { 109 ans = ans / i * ( i - 1 ); 110 do 111 { 112 n = n / i; 113 } 114 while ( n % i == 0 ); 115 } 116 } 117 if ( n > 1 ) 118 { 119 ans = ans / n * ( n - 1 ); 120 } 121 return ans; 122 } 123 124 int phi[N]; 125 126 void phi_table( int n ) 127 { 128 for ( int i = 1; i <= n; i++ ) 129 { 130 phi[i] = i; 131 } 132 for ( int i = 2; i <= n; i++ ) 133 { 134 if ( phi[i] == i ) 135 { 136 phi[i] = i - 1; 137 for ( int j = i + i; j <= n; j += i ) 138 { 139 phi[j] = phi[j] / i * ( i - 1 ); 140 } 141 } 142 } 143 }