所谓素数，是指恰好有两个约数的正整数。
- 埃氏筛法
- 区间筛法
- Miller-Rabin素性测试
判定单一的一个数是不是素数，素性测试：
Code
1bool is_prime(int n){ /* 判定一个数是不是素数 ，假设输入的数都是正整数 */
2 for (int i = 2; i * i <= n; i++) {
3 if (!(n % i)) return false;
4 }
5 return n != 1; /* 1是例外 */
6}
如果只对一个数进行素数测试，通常 $_math_inline$O(\sqrt{n})$math_inline_$ 的算法就足够了。但……..
Miller-Rabin素性测试
引理1(费马定理) 设p是素数，a为整数，且(a,p)=1，则 $_math_inline$a^{p-1} \equiv 1(\text{mod}p)$math_inline_$ 。
引理2(二次探测定理) 如果p是一个素数，且
$_math_inline$0 证明：易知
$_math_inline$x^2-1 \equiv 0(\text{mod}p)$math_inline_$
因为p是质数
$_math_inline$x=1或x=p-1$math_inline_$
虽然Wilson定理（对于给定的正整数n，n是素数的充要条件为
$_math_inline$(n-1)!\equiv -1(\text{mod}n)$math_inline_$
）给出了一个数是素数的充要条件，但是根据它来素性测试所需的计算量太大，无法实现对比较大整数的测试。目前，尽管高效的确定性素性算法尚未找到，但已有一些随机算法可用于素性测试及大整数的因式分解。 首先我们要知道费马定理只是n是素数的必要条件。即费马定理不成立，n一定是合数；费马定理成立，n可能是素数。 假设n是奇素数，则n-1必为偶数。令
$_math_inline$n-1=2^q\cdot m$math_inline_$
。 随机选取整数
$_math_inline$a(0 由二次探测定理可知：
$_math_inline$a^{2^{q-1}\cdot m} \equiv 1(\text{mod}n)$math_inline_$
或
$_math_inline$a^{2^{q-1}\cdot m} \equiv n-1(\text{mod}n)$math_inline_$
若
$_math_inline$a^{2^{q-1}\cdot m} \equiv 1(\text{mod}n)$math_inline_$
成立，则再次由二次探测定理可知：
$_math_inline$a^{2^{q-2}\cdot m} \equiv 1(\text{mod}p)$math_inline_$
或
$_math_inline$a^{2^{q-2}\cdot m} \equiv n-1(\text{mod}n)$math_inline_$
，…。如此反复应用二次探测定理，直到某一步
$_math_inline$a^m\equiv 1(\text{mod}n)$math_inline_$
或
$_math_inline$a^m\equiv n-1(\text{mod}n)$math_inline_$
。总之，若n是素数，则
$_math_inline$a^m\equiv 1(\text{mod}n)$math_inline_$
，或存在
$_math_inline$0\leq r \leq q-1$math_inline_$
，使
$_math_inline$a^{2^r\cdot m}\equiv n-1(\text{mod}n)$math_inline_$
所以该算法的过程为 若
$_math_inline$a^m\equiv1(\text{mod}n)$math_inline_$
，或者存在某个整数
$_math_inline$0\leq r \leq q-1$math_inline_$
，使
$_math_inline$a^{2^r\cdot m} \equiv n-1(\text{mod}p)$math_inline_$
成立，则称n通过Miller测试。 可以证明 Miller-Rabin 算法给出错误结果的概率小于等于
$_math_inline$\frac{1}{4}$math_inline_$
，若反复测试k次，则错误概率可降至
$_math_inline$(\frac{1}{4})^k$math_inline_$
。这是一个很保守的估计，实际使用的效果要好得多。 要枚举n以内的素数，可以用埃氏筛法：这是一种古老的算法，首先，将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去，然后表中剩余最小的素数是3，将表中所有3的倍数也都划去。以此类推，如果表中剩余最小的素数是m的话，就将表中所有m的倍数都划去，像这样反复操作，就能依次枚举n以内的素数，埃氏筛法的时间复杂度仅有
$_math_inline$O(nlogn)$math_inline_$
，接近线性： 目的： 找出a~b这个区间有几个质数，哪些是质数 做法： 在筛出
Code
1const int S = 8;
2
3LL mult_mod(LL a, LL b, LL c){
4 a %= c;
5 b %= c;
6 LL ret = 0;
7 LL tmp = a;
8 while(b){
9 if(b&1){
10 ret += tmp;
11 if(ret > c) ret -= c;
12 }
13 tmp <<= 1;
14 if(tmp > c) tmp -= c;
15 b >>= 1;
16 }
17 return ret;
18}
19
20LL pow_mod(LL a, LL n, LL mod){
21 LL ret = 1;
22 LL temp = a % mod;
23 while(n){
24 if(n & 1) ret = mult_mod(ret, temp, mod);
25 temp = mult_mod(temp, temp, mod);
26 n >>= 1;
27 }
28 return ret;
29}
30
31bool check(LL a, LL n, LL x, LL t){
32 LL ret = pow_mod(a, x, n);
33 LL last = ret;
34 loop(i, 1, t){
35 ret = mult_mod(ret, ret, n);
36 if(ret == 1 && last != 1 && last != n-1) return true;
37 last = ret;
38 }
39 if(ret != 1) return true;
40 else return false;
41}
42
43bool Miller_Rabin(LL n){
44 if(n < 2) return false;
45 if(n == 2) return true;
46 if((n&1)==0) return false;
47 LL x = n-1;
48 LL t = 0;
49 while((x&1)==0){x >>= 1; ++t;}
50 srand(time(NULL));
51 rep(i, S){
52 LL a = rand()%(n-1)+1;
53 if(check(a, n, x, t)) return false;
54 }
55 return true;
56}
埃氏筛法
Code
1bool is_prime[100];
2int prime[100];
3int sieve(int n) { /* 枚举n以内的素数 */
4 /* 返回n以内素数的个数，素数存在prime数组里 */
5 int p = 0;
6 for (int i = 0; i <= n; i++)
7 is_prime[i] = true;
8 is_prime[0] = is_prime[1] = false;
9 for (int i = 2; i <= n; i++) {
10 if (is_prime[i]) {
11 prime[p++] = i;
12 for (int j = i * 2; j <= n; j += i)
13 is_prime[j] = false;
14 }
15 }
16 return p;
17}
区间筛法
[0,sqrt(b)之间的素数的同时，将在[a,b)这个区间的之中的该素数的倍数都划掉。Code
1#include <iostream>
2#include <cstdio>
3#include <cstring>
4#include <algorithm>
5
6using namespace std;
7#define M 100000000
8typedef long long ll;
9bool is_prime_small[M];
10bool is_prime[M];
11ll ans = 0;
12
13void prime(ll a, ll b) {
14 for (ll i = 2; i * i < b; i++) is_prime_small[i] = true; //初始化2~b^(1/2)
15 for (ll i = 0; i < b - a; i++) is_prime[i] = true; //因为a,b很大，所以用0~b-a 代表a~b
16 for (ll i = 2; i * i < b; i++) {
17 if (is_prime_small[i]) {
18 for (ll j = 2 * i; j * j < b; j += i) is_prime_small[j] = false;
19 for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) { //找到从a开始的第一个合数
20 if (is_prime[j - a]) {
21 ans++; //求出几个合数。 //或者也可以最后遍历b-a这区间，求出质数的个数。
22 is_prime[j - a] = false;
23 }
24 }
25 }
26 }
27}
28
29int main() {
30 ll a, b;
31 ans = 0;
32 cin >> a >> b;
33 prime(a, b);
34 // for(ll i = 0;i < b-a;i++)
35 // if(is_prime[i]) ans++;
36 cout << "ans = " << b - a - ans << endl;
37 return 0;
38}
例题
Code
1#include <iostream>
2#include <cstdio>
3#include <algorithm>
4
5#define M 1000001
6
7using namespace std;
8
9int num[M];
10int is_prime[M];
11int ans[M];
12
13void slove() {
14 for (int i = 0; i < M; i++) is_prime[i] = true;
15 int k = 1;
16 num[1] = 0;
17 is_prime[1] = true;
18 for (int i = 2; i < M; i++) {
19 if (is_prime[i]) {
20 num[i] = k++;
21 ans[i] = num[i];
22 for (int j = 2 * i; j < M; j += i) {
23 is_prime[j] = false;
24 ans[j] = num[i];
25 }
26 }
27 }
28}
29
30int main() {
31 slove();
32 int a;
33 while (scanf("%d", &a) == 1) {
34 printf("%d\n", ans[a]);
35 }
36 return 0;
37}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。