一、什么叫质数

     质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数（也称为合成数）。例如，5是个素数，因为其正约数只有1与5。7是个素数，因为其正约数只有1与7。而4则是个合数，因为除了1与4外，2也是其正约数。6也是个合数，因为除了1与6外，2与3也是其正约数。算术基本定理确立了素数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一素数之乘积。为了确保该定理的唯一性，1被定义为不是素数，因为在因式分解中可以有任意多个1（如3、1×3、1×1×3等都是3的有效约数分解）。

二、试除法（暴力枚举）

1）穷举

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    for(int i = 2;i < n;i ++){ //这个很好理解，从最小的质数2开始枚举到n - 1
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}

时间复杂度为O(√n),但是这样消耗时间过长，我们需要优化，现在有三种优化方法，下面一一细说

2）使用sqrt()

bool is_prime(int n){
    if(n < 2) return false; //2是最小的质数，如果n小于2，那n肯定就不是质数
    for(int i = 2;i <= sqrt(n);i ++){ //优化部分
        if(n % i == 0){ //如果可以被i整除，说明这个数不是质数
            return false; //返回不是
        }
    }
    return true; //返回是
}

现在我们就可以从2枚举到√(n)，但是这种做法依旧不推荐，因为sqrt这个函数运行速度很慢，每次执行都要运算一遍

3）i*i<=n

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i * i <= n;i ++){ 
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

同样也不推荐这种算法，容易爆溢出

4）i<=n/i(推荐)

bool is_prime(int n){
    if(n < 2) return false;
    for(int i = 2;i <= n / i;i ++){ //优化内容
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

这种优化就不会出前几种方法的错误，因此比较推荐

三、素数筛

        素数筛（Prime Sieve）是一种用于生成一定范围内所有质数的算法。素数筛法通过排除非质数的方式来筛选出质数，从而提高质数的生成效率。

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

         埃拉托斯特尼筛法是一种用于生成一定范围内的所有质数的方法。它的基本思想是从2开始，将每个素数的倍数标记为非素数，直到遍历完所有小于N的数。剩下未标记的数即为质数。这种方法的时间复杂度为O(nlog(log(n)))

#include <iostream>
#include <vector>
using namespace std;

vector<bool> sieveOfEratosthenes(int n)
{
    // 创建一个长度为n+1的布尔向量，初始化为true
    vector<bool> isPrime(n + 1, true);
//由于数组的索引是从 0 开始的，所以我们需要将长度设置为 n + 1，以确保能够正确表示从 2 到 n 的所有数的状态。

    isPrime[0] = isPrime[1] = false; // 0和1不是质数

    // 根据埃拉托斯特尼筛法进行筛选
    for (int i = 2; i * i <= n; i++)
    {
        if (isPrime[i])
        {
            // 将i的倍数标记为非质数
            for (int j = i * i; j <= n; j += i)
            {
                isPrime[j] = false;
            }
        }
    }

    return isPrime;
}

int main()
{
    int n;
    cout << "请输入一个正整数n: ";
    cin >> n;

    vector<bool> primes = sieveOfEratosthenes(n);

    cout << "小于等于" << n << "的质数有: ";
    for (int i = 2; i <= n; i++)
    {
        if (primes[i])
        {
            cout << i << " ";
        }
    }

    return 0;
}

2、欧拉筛法

           欧拉筛法（Euler's Sieve）是一种高效的素数筛算法，用于生成一定范围内的所有质数。它是以瑞士数学家欧拉（Leonhard Euler）的名字命名的。

          欧拉筛法的基本思想是从小到大逐个筛选数，并且每个数只被它的最小质因数筛选一次。相比于埃拉托斯特尼筛法，欧拉筛法通过避免重复筛选相同的数值，提高了效率。欧拉筛法的时间复杂度为 O(n log log n)

#include <iostream>
#include <vector>
using namespace std;

vector<int> eulerSieve(int n) {
    vector<int> primes;//定义质数列表
    vector<bool> isPrime(n + 1, true);

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i); // 将质数加入质数列表

            // 将 i 的倍数标记为非质数
            for (int j = i * 2; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return primes;
}

int main() {
    int n;
    cout << "请输入一个正整数 n: ";
    cin >> n;

    vector<int> primes = eulerSieve(n);

    cout << "小于等于 " << n << " 的质数有: ";
    for (int prime : primes) {
        cout << prime << " ";
    }
    cout << endl;

    return 0;
}

3、线性筛法

参考：线性筛法解析-CSDN博客

           线性筛法（Linear Sieve）是一种高效的质数筛选算法，用于生成小于等于给定数n的所有质数。

           其基本思想是通过遍历每个数，同时维护一个最小质因数数组，来进行筛选。线性筛法的核心是利用每个合数都会被其最小质因数筛选一次这一性质，避免了重复筛选。线性筛法的时间复杂度为 O(n)

#include <iostream>
#include <vector>
using namespace std;

void getPrimes(int n) {
    vector<int> primes; // 存放质数的数组
    vector<bool> st(n + 1, false); // 标记数组，初始时都为false
    int cnt = 0; // 质数个数

    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes.push_back(i); // 将i加入质数数组
            cnt++;
        }

        for (int j = 0; j < cnt && primes[j] <= n/i; j++) {
            st[primes[j] * i] = true; // 标记合数
            if (i % primes[j] == 0)
                break; // primes[j]是i的最小质因数
        }
    }

    // 输出质数数组
    cout << "小于等于 " << n << " 的质数有: ";
    for (int prime : primes) {
        cout << prime << " ";
    }
    cout << endl;
}

int main() {
    int n;
    cout << "请输入一个正整数 n: ";
    cin >> n;

    getPrimes(n);

    return 0;
}

在第二个for循环中，将primes[ j ]的 i 倍筛掉（i 是从小到大依次遍历）

若存在一个合数X，设primes[ j ] 是它的最小质因子，当 i 枚举到X之前，一定会先枚举到X / primes[ j ]，而在那时，就已经先将X筛掉了。所以任何一个合数一定会被筛掉，是因为我们只用最小质因子来筛，但每个数只有一个最小质因子，所以每个数都只会筛一遍。例如 X = 12，2是12的最小质因子，在枚举到12之前一定会先枚举到6，并执行了st[ 2 * 6] = true，所以 i == 12 时，不会进入primes[ j ]数组  ；

示例： 

当我们使用输入值 n = 20 来演示线性筛法的代码时，让我们一步一步地执行代码并跟踪变量的变化。

  1. 初始化变量：

    • n = 20
    • primes = []
    • st = [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false]
    • cnt = 0

  2. 第一次循环，i = 2：

    • st[2] 为 false，将 2 加入 primes 数组，primes = [2]，cnt = 1
    • j 不满足条件 primes[j] <= n / i，因为 primes[j] = 2，而 n / i = 20 / 2 = 10
    • st[4] 被标记为 true，因为 primes[0] * i = 2 * 2 = 4
    • st[6] 被标记为 true，因为 primes[0] * i = 2 * 3 = 6
    • st[8] 被标记为 true，因为 primes[0] * i = 2 * 4 = 8
    • st[10] 被标记为 true，因为 primes[0] * i = 2 * 5 = 10
    • st[12] 被标记为 true，因为 primes[0] * i = 2 * 6 = 12
    • st[14] 被标记为 true，因为 primes[0] * i = 2 * 7 = 14
    • st[16] 被标记为 true，因为 primes[0] * i = 2 * 8 = 16
    • st[18] 被标记为 true，因为 primes[0] * i = 2 * 9 = 18
    • st[20] 被标记为 true，因为 primes[0] * i = 2 * 10 = 20

  3. 第二次循环，i = 3：

    • st[3] 为 false，将 3 加入 primes 数组，primes = [2, 3]，cnt = 2
    • j 不满足条件 primes[j] <= n / i，因为 primes[j] = 2，而 n / i = 20 / 3 = 6
    • st[6] 已经标记为 true，跳过标记步骤

  4. 第三次循环，i = 4：

    • st[4] 已经标记为 true，跳过标记步骤

  5. 第四次循环，i = 5：

    • st[5] 为 false，将 5 加入 primes 数组，primes = [2, 3, 5]，cnt = 3
    • j 不满足条件 primes[j] <= n / i，因为 primes[j] = 2，而 n / i = 20 / 5 = 4
    • st[10] 已经标记为 true，跳过标记步骤

  6. 第五次循环，i = 6：

    • st[6] 已经标记为 true，跳过标记步骤

  7. 第六次循环，i = 7：

    • st[7] 为 false，将 7 加入 primes 数组，primes = [2, 3, 5, 7]，cnt = 4
    • j 不满足条件 primes[j] <= n / i，因为 primes[j] = 2，而 n / i = 20 / 7 = 2
    • st[14] 已经标记为 true，跳过标记步骤

  8. 第七次循环，i = 8：

    • st[8] 已经标记为 true，跳过标记步骤

  9. 第八次循环，i = 9：

    • st[9] 为 false，将 9 加入 primes 数组，primes = [2, 3, 5, 7, 9]，cnt = 5
    • j 不满足条件 primes[j] <= n / i，因为 primes[j] = 2，而 n / i = 20 / 9 = 2
    • st[18] 已经标记为 true，跳过标记步骤

  10. 第九次循环，i = 10：

    • st[10] 已经标记为 true，跳过标记步骤

  11. 第十次循环，i = 11：

    • st[11] 为 false，将 11 加入 primes 数组，primes = [2, 3, 5, 7, 9, 11]，cnt = 6
    • j 不满足条件 primes[j] <= n / i，因为 primes[j] = 2，而 n / i = 20 / 11 = 1
    • st[22] 超出了数组范围，跳过标记步骤

  12. 第十一次循环，i = 12：

    • st[12] 已经标记为 true，跳过标记步骤

  13. 第十二次循环，i = 13：

    • st[13] 为 false，将 13 加入 primes 数组，primes = [2, 3, 5, 7, 9, 11, 13]，cnt = 7
    • j 不满足条件 primes[j] <= n / i，因为 primes[j] = 2，而 n / i = 20 / 13 = 1
    • st[26] 超出了数组范围，跳过标记步骤

  14. 第十三次循环，i = 14：

    • st[14] 已经标记为 true，跳过标记步骤

  15. 第十四次循环，i = 15：

    • st[15] 为 false，将 15 加入 primes 数组，primes = [2, 3, 5, 7, 9, 11, 13, 15]，cnt = 8
    • j 不满足条件 primes[j] <= n / i，因为 primes[j] = 2，而 n / i = 20 / 15 = 1
    • st[30] 超出了数组范围，跳过标记步骤

  16. 第十五次循环，i = 16：

    • st[16] 已经标记为 true，跳过标记步骤

依次类推，最终得到所有质数

四、米勒-拉宾素性测试

参考：米勒-拉宾素性检验(MillerRabbin)算法详解_米勒拉宾素性检验-CSDN博客

            米勒-拉宾素性测试（Miller-Rabin Primality Test）是一种用于确定一个数是否为素数的概率性算法。与确定性素性测试算法不同，米勒-拉宾素性测试可以在有限的步骤内确定一个数是否为合数，但对于素数则只能给出一个概率性的判断。

1、费马小定理

米勒-拉宾素性测试的基本思想是利用费马小定理（Fermat's Little Theorem）。费马小定理指出，如果一个数p是素数，那么对于任意整数a（1 < a < p），都满足以下关系：

a^(p-1) ≡ 1 (mod p)

这个公式 a^(p-1) ≡ 1 (mod p) 是费马小定理（Fermat's Little Theorem）的表达式。它表明，如果 p 是一个素数，且 a 是不被 p 整除的任意整数，那么 a 的（p-1）次方除以 p 的余数将等于 1。

根据费马小定理，如果对于一个合数n，存在一个整数a满足：

a^(n-1) ≢ 1 (mod n)

那么n一定是合数。

2、二次探测

对于任意一个小于p的正整数x，发现1（模p）的非平凡平方根存在，则说明p是合数。

我们把 1和-1称为 平凡根   其他的根都称为非平凡根

而 如果一个数x 的平方 模 p =1 或-1   我们就称这个数是1 或 -1 模p 的非平凡平方根

然而  ≡ -1 (mod p)  那x就是虚数了 不在我们讨论范围内  所以  我们只用关心  ≡ 1(mod p)  

也就是只用关心 1（模p）的非平凡平方根  而如果p是素数 那么 他的根只可能是 1或者 p-1

若根不是1或者p-1 那他就是个合数     关于证明 在下边

如果p是一个素数，0 < x< p,   则方程 x^{2} ≡ 1(mod p) 的解为 x=1 ,x= p-1

反之 如果  x^ 2 ≡ 1(mod p)  的解不是 x=1 ,x= p-1   那 p 就不是素数

#include <iostream>
#include <cstdlib>
#include <cmath>

// 计算 (a^b) % m 的快速幂算法
long long fastPower(long long a, long long b, long long m) {
    long long result = 1;  // 初始结果为 1
    a %= m;  // 对底数 a 进行取模运算，以防溢出或得到不准确的结果
    while (b > 0) {
        if (b & 1) {  // 如果当前二进制位的值为 1
            result = (result * a) % m;  // 累乘当前的底数 a，并对结果取模 m
        }
        a = (a * a) % m;  // 更新底数 a 的值为 a^2，并对结果取模 m
        b >>= 1;  // 将指数右移一位，相当于除以 2
    }
    return result;  // 返回最终结果
}

// 米勒-拉宾素性测试
bool millerRabin(long long n, int k) {
    if (n == 2 || n == 3) {
        return true;//如果 n 是 2 或 3，则直接返回 true。这是因为 2 和 3 都是素数。
    }
    if (n <= 1 || n % 2 == 0) {
        return false;//如果 n 小于等于 1 或者为偶数（除了 2），则直接返回 false。这是因为素数定义大于 1，且偶数除了 2 都不是素数。
    }

    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {  // 计算 d 和 r 的值，使得 n-1 = 2^r * d
        d /= 2;
        r++;
    }

    for (int i = 0; i < k; i++) {  // 进行 k 次测试
        long long a = 2 + rand() % (n - 3);  // 随机选择一个底数 a，范围为 [2, n-2]
        long long x = fastPower(a, d, n);  // 计算 a^d % n

        if (x == 1 || x == n - 1) {  // 如果 a^d % n 等于 1 或者 n-1，则可能是素数，进行下一次测试
            continue;
        }

        bool isPrime = false;
        for (int j = 0; j < r - 1; j++) {  // 进行 r-1 次平方测试
            x = fastPower(x, 2, n);  // 计算 x^2 % n
            if (x == n - 1) {  // 如果 x^2 % n 等于 n-1，则可能是素数，终止内层循环
                isPrime = true;
                break;
            }
        }

        if (!isPrime) {  // 如果经过 r-1 次平方测试后，未满足条件，则 n 不是素数，返回 false
            return false;
        }
    }

    return true;  // 经过 k 次测试后，n 可能是素数，返回 true
}
int main() {
    long long n;
    int k;
    std::cout << "Enter a number: ";
    std::cin >> n;
    std::cout << "Enter the number of tests: ";
    std::cin >> k;

    if (millerRabin(n, k)) {
        std::cout << n << " is probably prime." << std::endl;
    } else {
        std::cout << n << " is composite." << std::endl;
    }

    return 0;
}

 对于fastPower的示例：

假设我们要计算 (3^13) % 7 的结果，即 a = 3，b = 13，m = 7。

初始时，result = 1，a = 3 % 7 = 3，b = 13。

第一次循环：b 的二进制表示为 1101，最低位为 1。因此，我们将 result = (result * a) % m，即 result = (1 * 3) % 7 = 3。
同时，更新 a 的值为 a = (a * a) % m，即 a = (3 * 3) % 7 = 2。
将 b 右移一位得到 b = 110。

第二次循环：b 的二进制表示为 110，最低位为 0。此时不需要累乘 a，因此结果保持不变：result = 3。
同时，更新 a 的值为 a = (a * a) % m，即 a = (2 * 2) % 7 = 4。
将 b 右移一位得到 b = 11。

第三次循环：b 的二进制表示为 11，最低位为 1。累乘 a：result = (result * a) % m，即 result = (3 * 4) % 7 = 5。
同时，更新 a 的值为 a = (a * a) % m，即 a = (4 * 4) % 7 = 2。
将 b 右移一位得到 b = 1。

第四次循环：b 的二进制表示为 1，最低位为 1。累乘 a：result = (result * a) % m，即 result = (5 * 2) % 7 = 3。
同时，更新 a 的值为 a = (a * a) % m，即 a = (2 * 2) % 7 = 4。
将 b 右移一位得到 b = 0。

由于 b 的值为 0，循环结束，最终结果为 result = 3，即 (3^13) % 7 = 3。

米勒-拉宾素性测试示例：

假设我们要使用米勒-拉宾素性测试来判断数 21 是否为素数，并进行 3 次测试（k = 3）。

我们首先检查特殊情况，如果 n 是 2 或 3，直接返回 true。但在这个例子中，21 不是 2 或 3，因此我们继续执行。

我们检查 n 是否小于等于 1 或为偶数（除了 2），如果是，则直接返回 false。在这个例子中，21 不是小于等于 1 且不是偶数，因此我们继续执行。

我们计算 n-1 的因子分解。对于 21，n-1 等于 20，可以写成 20 = 2^2 * 5。因此，d = 5，r = 2。

我们进行 3 次测试，每次选择一个随机的底数 a，在范围 [2, n-2] 内选择。

a) 假设我们选择 a = 7。

计算 a^d % n，即 7^5 % 21。我们可以使用快速幂算法进行计算，得到 7^5 % 21 = 7。

由于 7 不等于 1 且不等于 21-1=20，我们继续进行平方测试。

进行 r-1=2-1=1 次平方测试，计算 7^2 % 21 = 16。

结果不等于 1，因此我们得出结论：21 不是素数，返回 false。

因为我们只进行了一次测试，所以我们继续进行下一次测试。

b) 假设我们选择 a = 11。

计算 a^d % n，即 11^5 % 21。使用快速幂算法，得到 11^5 % 21 = 4。

由于 4 不等于 1 且不等于 21-1=20，我们继续进行平方测试。

进行 r-1=2-1=1 次平方测试，计算 4^2 % 21 = 16。

结果不等于 1，因此我们继续进行下一次测试。

c) 假设我们选择 a = 5。

计算 a^d % n，即 5^5 % 21。使用快速幂算法，得到 5^5 % 21 = 5。

由于 5 不等于 1 且不等于 21-1=20，我们继续进行平方测试。

进行 r-1=2-1=1 次平方测试，计算 5^2 % 21 = 4。

结果不等于 1，因此我们继续进行下一次测试。

我们完成了所有的 3 次测试，并且每次测试都未通过，因此我们得出结论：21 不是素数，返回 false。

本篇文章仅作为笔记来进行学习参考，并无其他用途 

# 算法
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

Llama 4 结果数据造假，Yann LeCun 接受 FT 采访爆料

avatar 2048 AI社区

C++模板：告别重复代码的利器

在开始今天的内容之前，我们先来看一下我们前面写过的交换函数：代码语言：javascriptAI代码解释//……我们看到，当想要交换int类型，double类型，char类型的数据，我们是不是要对各种类型的数据写对应的交换函数，ok，在我们还没有学函数重载的时候，甚至还要给这些交换不同类型的交换函数命不同的名字，现在我们学了函数重载，虽然可以实现，但是有一下几个不好的地方：重载的函数仅仅是类型不同，

avatar 2048 AI社区
cover

Phaser原理与落地实战

avatar 2048 AI社区