素数的定义

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

1.试除法（Trial Division）

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

步骤：

优点：

• 简单易懂

缺点：

• 效率较低，特别是当 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++代码：

仅包含子函数和子函数必要的头文件

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++代码：

仅包含子函数和子函数必要的头文件

#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）

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

步骤：

优点：

缺点：

• 是概率算法，不能提供确定性的结果（但通过多次实验，可以达到很高的精确度）

C++代码：

仅包含子函数和子函数必要的头文件

#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 次测试可以获得非常高的精度，适用于大数素性判断。

总结

• 试除法：适用于小规模的素数判断。
• 埃拉托斯特尼筛法：适合生成一段范围内的所有素数。
• 米勒-拉宾素性测试：适用于大数的素性测试，具有较高的效率和较高的准确性。

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

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

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