素数计算常用算法

作者: Pavilion_Cat
Icon发表于2024-12-26
Icon更新于2025-12-22
Icon访问量:
Icon算法
Icon

素数的定义

“质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数”

1. 试除法（Trial Division）

这是最基本的素数判断方法。判断一个数是否为素数，就是尝试除以所有小于它的整数，若没有整除的情况，则该数为素数。

试除法步骤

  • 如果一个数 n 能被小于 n 的某个整数整除，则 n 不是素数。
  • 最多只需要尝试除到 sqrt{n}​，因为如果 n=a×b，那么必有 a≤sqrt{n} 且 b≥sqrt{n}​，所以只需要检查小于等于 sqrt{n}​ 的数。
  • 简单易懂
  • 效率较低，特别是当 n 很大时

6k±1法优化的原理

除了 2 和 3 之外，所有素数都可以表示为 6k±1 的形式，其中k是一个整数。这是因为，任何整数 n 都可以写成以下六种形式之一：

6k，6k+1，6k+2，6k+3，6k+4，6k+5

在这些形式中，只有 6k+1 和 6k−1 可能是素数。其他形式都可以被 2 或 3 整除，因此不需要检查。

步骤

在标准的试除法中，通常需要从 2 开始检查每个数是否是素数。但在使用 6k±1 法时，我们可以跳过能被 2 或 3 整除的数，只检查形如 6k±1的数。

具体如下：

  1. 检查 n 是否能被 2 或 3 整除。如果可以，直接返回 false（不是素数）
  2. 从 5 开始，检查 n 是否能被形如 6k±1 的数整除，直到 sqrt{n} 为止

C++代码

1
2
3
4
5
6
7
8
9
10
11
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    // 检查从 5 开始的奇数因子
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}
  • 时间复杂度： O(sqrt{n})
  • 适用场景： 当 n 较小，或者只需要判断一个单独的数是否为素数时，试除法是最直接的选择

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

这是一个高效的生成素数的算法，可以用来找出一定范围内的所有素数。

筛法步骤

  • 创建一个从 2 到某个上限 n 的列表，初始时假设所有数都是素数
  • 从 2 开始，标记所有 2 的倍数为非素数（即删除）
  • 继续检查下一个未被删除的数，将其倍数删除
  • 重复上述过程直到所有小于 sqrt{n}​ 的数都处理完毕
  • 可以高效地找出一段区间内所有的素数
  • 时间复杂度为 O(n log ⁡log⁡ n)，比试除法要高效得多
  • 对于大范围的素数计算，内存占用较大

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector>

std::vector<bool> sieveOfEratosthenes(int n) {   //一个布尔向量，标记从0到n每个数是否为素数。
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    return isPrime;
}
  • 时间复杂度： O(n log log n)
  • 适用场景： 生成小于某个数 n 的所有素数时，埃拉托斯特尼筛法非常高效。对于处理大量素数查找任务，它的效率远高于试除法。

3. 米勒-拉宾素性测试（Miller-Rabin Primality Test）

这是一种概率性的素性测试算法。它判断一个数是否为素数，虽然它不能保证绝对正确，但通过多次测试可以以极高的概率确定一个数是否为素数。

步骤

  • 基于费马小定理：对于一个大素数 p，若随机选择的数 a 满足 ap−1≡1 mod p，则 p 是素数
  • 通过随机选择多个不同的 a，每次执行费马测试，若结果不成立，则 n 一定不是素数
  • 对于大数非常高效
  • 可以非常快速地进行素数性检验
  • 是概率算法，不能提供确定性的结果（但通过多次实验，可以达到很高的精确度）

C++代码

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
45
46
47
#include <cmath>
#include <cstdlib>

// 计算 (a^b) % mod
long long modExp(long long a, long long b, long long mod) {
    long long result = 1;
    while (b > 0) {
        if (b % 2 == 1) {
            result = (result * a) % mod;
        }
        a = (a * a) % mod;
        b /= 2;
    }
    return result;
}

bool millerRabinTest(long long n, int k) {
    if (n <= 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    
    // 将 n-1 分解成 d * 2^r
    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }
    
    for (int i = 0; i < k; i++) {
        long long a = 2 + rand() % (n - 4);  // 随机选择 a
        long long x = modExp(a, d, n);
        
        if (x == 1 || x == n - 1) continue;
        
        bool continueLoop = false;
        for (int j = 0; j < r - 1; j++) {
            x = (x * x) % n;
            if (x == n - 1) {
                continueLoop = true;
                break;
            }
        }
        if (!continueLoop) return false;
    }
    return true;
}
  • 时间复杂度： 每次测试的时间复杂度为 O(log n),进行 k 次测试，整体复杂度为 O(k log n)，其中 k 通常设置为 5 到 10，保证很高的精确度。
  • 适用场景： 对于大数素性检测，尤其是在确定性测试需求不高的情况下，米勒-拉宾测试非常高效。通过增加 kkk 次测试可以获得非常高的精度，适用于大数素性判断。

总结

算法对比

试除法

适用于小规模的素数判断

埃拉托斯特尼筛法

适合生成一段范围内的所有素数

米勒-拉宾素性测试

适用于大数的素性测试，具有较高的效率和较高的准确性

最低时间复杂度：埃拉托斯特尼筛法

适合大数素性检测：米勒-拉宾素性测试

因此，如果你需要找出一个区间内的所有素数，埃拉托斯特尼筛法 是最佳选择。如果是对大数的单独素性检测，米勒-拉宾素性测试 会更有效。

Icon倘若帮到您，赏根猫条呗～ 嘿嘿
QRCode微信赞赏
QRCode支付宝
本作品由 Pavilion_Cat 于 2024-12-26 13:48:00 发布
作品地址：素数计算常用算法
除特别声明外，本站作品均采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 Pavilion_Cat's Blog
Logo