埃氏筛法和线性筛法求素数

在计算机科学中，素数是指大于1的自然数，除了1和本身以外，没有其他的因数。素数在计算机科学和密码学等领域有着广泛的应用，如质因数分解、RSA加密等。

计算素数是一个常见的数学问题，常见的解法包括暴力枚举、试除法、埃氏筛法和线性筛法等。

下面我们详细介绍一下埃氏筛法和线性筛法这两种求素数的算法。

埃氏筛法

埃氏筛法，又称筛法求素数，是一种简单有效的求素数的方法。其基本思想是，首先将所有的数标记为素数，然后从2开始枚举每个素数，将它的倍数标记为合数。这样一直枚举下去，最终剩下的未被标记的数就是素数。

下面是使用 C++ 实现埃氏筛法的代码：

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

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;

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

    return is_prime;
}

int main() {
    int n = 30;
    vector<bool> is_prime = sieve(n);

    for (int i = 0; i <= n; i++) {
        if (is_prime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

代码中的 sieve 函数接受一个整数 n，返回一个长度为 n + 1 的布尔类型的数组，数组中的元素表示对应的数是否是素数。在函数中，我们首先将所有的数标记为素数，然后从2开始枚举每个素数，将它的倍数标记为合数。最后返回标记结果。

在主函数中，我们调用 sieve 函数来求解 1 到 30 中的所有素数，并将结果输出到控制台上。输出结果为：

2 3 5 7 11 13 17 19 23 29

从输出结果可以看出，1 到 30 中的所有素数分别为2、3、5、7、11、13、17、19、23和29，与前面我们手算的结果一致。

需要注意的是，埃氏筛法的时间复杂度是 O(n log log n)，其中 n 是输入的范围。在实际应用中，由于该算法的空间复杂度较高，仅适用于求解较小

接下来，我将分别介绍埃氏筛法和线性筛法的实现原理和代码实现。

埃氏筛法

埃氏筛法是一种简单的筛法，它的基本思想是：从小到大枚举素数，然后将它的倍数都标记为合数，直到筛完所有小于等于目标数的数。具体实现过程如下：

1. 创建一个长度为 $n+1$ 的布尔数组 $prime$，其中 $prime[i]$ 表示 $i$ 是否为素数，初始时所有元素都设置为 true。

2. 从 2 开始，枚举 $i$，如果 $prime[i]$ 为 true，则说明 $i$ 是素数，将 $i$ 的所有倍数（除了 $i$ 本身）都标记为合数，即将 $prime[j]$ 设为 false，其中 $j=i+1, 2i+1, 3i+1, \\ldots, ni+1$，直到 $ni+1>n$。

3. 扫描数组 $prime$，将所有值为 true 的下标输出，即可得到小于等于 $n$ 的所有素数。

下面是用 C++ 实现的埃氏筛法代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> Eratosthenes(int n) {
    vector<int> primes;
    vector<bool> prime(n + 1, true); // 初始化所有数为素数

    for (int i = 2; i <= n; ++i) {
        if (prime[i]) { // i 是素数
            primes.push_back(i);
            for (int j = i * 2; j <= n; j += i) { // 标记 i 的倍数为合数
                prime[j] = false;
            }
        }
    }

    return primes;
}

int main() {
    int n = 100;
    vector<int> primes = Eratosthenes(n);

    for (int prime : primes) {
        cout << prime << " ";
    }
    cout << endl;

    return 0;
}

线性筛法

埃氏筛法的时间复杂度为 $O(n\\log\\log n)$，其中 $\\log\\log n$ 是素数个数的阶数。虽然时间复杂度已经很小了，但对于非常大的数仍然不够快。线性筛法是一种优化的算法，它在埃氏筛法的基础上进一步优化了时间复杂度，使得求解范围更大的素数变得可行。

线性筛法的核心思想是：每个合数只会被它的最小质因子筛掉，因此一个数不可能被多次筛掉，这样就避免了重复标记的问题。具体实现过程如下：

1. 创建一个长度为 $n+1$ 的整型数组 $prime$，其中 $prime[i]$ 表示 $i

在埃氏筛法中，我们从最小的素数开始，将其倍数标记为合数，直到筛子的尽头。这种方法虽然简单，但需要标记很多数，导致时间复杂度较高。因此，出现了另一种更高效的方法，称为线性筛法。

线性筛法可以同时筛选素数和合数，并且只需要标记一次。基本思想是，对于每个合数，我们可以找到其最小的素因子。在筛选过程中，我们不会再将其标记为合数，而是直接将其最小的素因子记录下来，从而减少了标记次数。

下面是线性筛法的步骤：

1. 从小到大枚举每个数i。

2. 如果i是素数，则将其加入素数数组中，并将其最小的素因子设为它自身。

3. 枚举素数数组中的每个数p，如果i * p超过了最大的数n，则结束循环；否则，如果i % p等于0，则说明i * p的最小素因子为p，将i * p的最小素因子设为p，并退出循环。

4. 如果i的最小素因子为它本身，则说明i是素数。

下面是用C++实现的线性筛法代码：

vector<int> prime; // 存储素数
int is_prime[N]; // is_prime[i] = 0表示i是素数，is_prime[i] != 0表示i的最小素因子

void linear_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (is_prime[i] == 0) {
            prime.push_back(i);
            is_prime[i] = i;
        }
        for (int j = 0; j < prime.size() && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = prime[j];
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

在这个实现中，我们使用一个素数数组prime来存储素数，并使用一个数组is_prime来存储每个数的最小素因子。在主循环中，我们依次枚举每个数i，并根据i的最小素因子的不同情况进行相应的处理。具体而言：

• 如果i是素数，则将其加入素数数组中，并将其最小素因子设为它本身。

• 如果i不是素数，则枚举素数数组中的每个数p，如果i * p超过了最大的数n，则结束循环；否则，如果i % p等于0，则说明i * p的最小素因子为p，将其最小素因子设为p，并退出循环。

• 如果i的最小素因子为它本身，则说明i是素数。

这样，我们就得到了一组连续的素数。