跳转至

质数筛

下面是每种质数筛法的核心代码和详细注释。

1. 埃拉托斯特尼筛法（Sieve of Eratosthenes）

  • 从2开始，依次筛选掉每个质数的倍数，剩下的就是质数。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>

// 埃拉托斯特尼筛法，找出小于等于n的所有质数
void sieveOfEratosthenes(int n) {
    std::vector<bool> prime(n+1, true); // 标记是否为质数，默认为true
    prime[0] = prime[1] = false; // 0和1不是质数，标记为false
    for (int p = 2; p * p <= n; p++) { // 从2开始，只需检查到sqrt(n)
        if (prime[p]) { // 如果p是质数
            for (int i = p * p; i <= n; i += p) // 从p^2开始，标记p的倍数为非质数
                prime[i] = false;
        }
    }
    for (int p = 2; p <= n; p++) // 打印所有质数
        if (prime[p])
            std::cout << p << " ";
}

2. 线性筛法（Linear Sieve）

  • 可以同时找出一定范围内的所有质数和每个合数的最小质因数，其时间复杂度接近线性。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>

// 线性筛法，找出小于等于n的所有质数和每个合数的最小质因数
void linearSieve(int n) {
    std::vector<int> prime(n + 1, 0); // 存储每个数的最小质因数
    std::vector<int> minPrime(n + 1, 0); // 存储每个数的最小质因数
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) { // 如果i是质数
            prime[i] = i; // 最小质因数是它自己
            minPrime[i] = i;
        }
        for (int j = i; j <= n; j += i) { // 标记i的倍数
            prime[j] = i; // j的最小质因数是i
            if (minPrime[j] == 0 || prime[minPrime[j]] > prime[i]) // 更新最小质因数
                minPrime[j] = i;
        }
    }
    // 输出质数和最小质因数
    for (int i = 2; i <= n; i++) {
        if (prime[i] == i) // 如果最小质因数是它自己，则是质数
            std::cout << i << " ";
    }
}

3. 欧拉筛法（Euler's Sieve）

  • 欧拉筛法利用了欧拉函数的性质，通过计算小于或等于给定数的所有整数的欧拉函数值来筛选质数。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>

// 欧拉筛法，找出小于等于n的所有质数
void eulerSieve(int n) {
    std::vector<int> prime(n + 1, 0); // 存储每个数的最小质因数
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) { // 如果i是质数
            for (int j = i; j <= n; j += i) { // 标记i的倍数
                prime[j] = i; // j的最小质因数是i
            }
        }
    }
    for (int i = 2; i <= n; i++) { // 打印所有质数
        if (prime[i] == i) // 如果最小质因数是它自己，则是质数
            std::cout << i << " ";
    }
}

4. 梅森筛法（Mersenne's Sieve）

  • 梅森筛法专门用于找出梅森质数（形如 \(2^p−1\) 的质数），它通过筛选掉那些 \(2^p−1\) 不是质数的 p 值。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>

// 梅森筛法，找出小于等于p的所有梅森质数
void mersenneSieve(int p) {
    std::vector<bool> mersenne(p + 1, true); // 标记是否为梅森质数，默认为true
    mersenne[0] = mersenne[1] = false; // 0和1不是梅森质数，标记为false
    for (int i = 2; (i * i) <= p; i++) { // 只需检查到sqrt(p)
        if (mersenne[i]) { // 如果i是梅森质数
            for (int j = (i * i); j <= p; j += i) // 从i^2开始，标记i的倍数为非梅森质数
                mersenne[j] = false;
        }
    }
    for (int i = 2; i <= p; i++) { // 打印所有梅森质数
        if (mersenne[i])
            std::cout << "Mersenne Prime: 2^" << i << " - 1 = " << (1ULL << i) - 1 << std::endl;
    }
}

5. 轮筛法（Wheel Factorization）

  • 轮筛法通过预先移除一些常见的因子（如2、3、5等）的倍数，来减少埃氏筛法中的冗余计算。
 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
#include <iostream>
#include <vector>

// 轮筛法，找出小于等于n的所有质数
void wheelFactorization(int n) {
    const int wheelSize = 4; // 使用2, 3, 5作为轮子
    std::vector<int> wheel = {1, 2, 3, 5}; // 轮子数组
    std::vector<bool> isPrime(n + 1, true); // 标记是否为质数，默认为true
    std::vector<int> wheelPos(wheelSize, 0); // 存储每个轮子的位置
    isPrime[0] = isPrime[1] = false; // 0和1不是质数，标记为false
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) { // 如果i是质数
            for (int j = 0; j < wheelSize; j++) { // 标记i的倍数
                int multiple = i * wheel[j] + wheelPos[j];
                if (multiple > i) {
                    wheelPos[j] = 0; // 重置位置
                    continue;
                }
                if (multiple <= n) {
                    isPrime[multiple] = false; // 标记为非质数
                    wheelPos[j] = (wheelPos[j] + 1) % wheel[j]; // 更新位置
                }
            }
        }
    }
    for (int i = 2; i <= n; i++) { // 打印所有质数
        if (isPrime[i])
            std::cout << i << " ";
    }
}

6. 阿特金筛法（Atkin's Sieve）

Atkin's Sieve是一种现代的质数筛法，它基于数论中的同余性质。它不仅可以找出一定范围内的所有质数，还可以找出所有合数的最小质因数。Atkin's Sieve的核心思想是利用模8同余的性质来减少筛选的计算量。

核心思想： 对于每个整数 n，如果 n 满足以下条件之一，则 n 必定是合数：

  1. n%4≡1 且 n 是完全平方数。
  2. n%8≡4 且 n 是两倍的完全平方数。
  3. n%8≡7 且 n 是三倍的完全平方数。
  4. n%16≡8,9,10,13,14,15。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>

// Atkin筛法，找出小于等于n的所有质数
void atkinsSieve(int n) {
    std::vector<bool> isPrime(n + 1, true); // 标记是否为质数，默认为true
    std::vector<int> prime; // 存储质数
    isPrime[0] = isPrime[1] = false; // 0和1不是质数，标记为false
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) { // 如果i是质数
            for (int j = i; j <= n; j += i) { // 标记i的倍数为非质数
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) { // 存储所有质数
        if (isPrime[i])
            prime.push_back(i);
    }
    // 输出质数
    for (int p : prime)
        std::cout << p << " ";
}

7. 普拉查-尼文-蒙哥马利筛法（Prachar-Niven-Montgomery Sieve）

  • 普氏筛是一种高效的质数筛法，特别适用于找出小于等于 n 的所有质数。它基于以下性质：如果 p 是质数，那么 \(2^p≡2(mod p^2)\)。

  • 初始化一个布尔数组，长度为 n+1，所有元素初始为 true。

  • 从 i=2 开始，如果 i 是质数，则标记 i 的所有倍数为 false。
  • 对于每个 i，检查 \(2^i mod  i^2\) 是否等于 1，如果不是，则 i 是合数。

原理：费马小定理

 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
#include <iostream>
#include <vector>
#include <cmath>

void pracharNivenMontgomerySieve(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 检查每个数是否满足费马小定理
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            int power = 1;
            for (int j = 0; j < 10; j++) { // 检查10次以提高准确性
                int temp = power * power % (i * i);
                if (temp == 1) {
                    isPrime[i] = false;
                    break;
                } else {
                    power = temp;
                }
            }
        }
    }

    // 输出质数
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }

    for (int p : primes) {
        std::cout << p << " ";
    }
}