质数的统计（区域范围内的个数）

Question

请各位指导一下 欧拉筛 的原理及代码，谢谢，网上的公式真的看不懂

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

欧拉筛（Euler Sieve），也称为线性筛，是一种高效的算法，用于生成一定范围内的所有素数。它的时间复杂度为O(n)，空间复杂度为O(n)。以下是欧拉筛的原理及C++实现的详细说明。

欧拉筛的工作原理和算法步骤：

1. 初始化：创建一个布尔数组isPrime，长度为n+1，用于标记每个数字是否为素数。初始时，除了isPrime[1]设为false（因为1不是素数），其余所有元素设为true。

2. 筛选素数：从2开始，遍历每个数字i，如果isPrime[i]为true，则i是一个素数。将i添加到素数列表中。

3. 标记合数：对于每个素数i，遍历它的所有倍数i*j（j从2开始），将它们标记为非素数（isPrime[i*j] = false）。当i能被j整除时（i % j == 0），停止内层循环，因为后续的i*j将包含更小的素因子，这些合数将由这些更小的素因子来标记。

4. 继续遍历：重复步骤2和3，直到遍历完所有小于等于n的数字。

5. 统计素数：最后，素数列表中的元素即为指定区域内的所有素数，可以通过遍历isPrime数组来统计素数的个数。

C++实现欧拉筛的代码示例：

#include <iostream>
#include <vector>
#include <cstring>

const int MAXN = 1000001; // 根据需要调整最大范围
bool isPrime[MAXN];
std::vector<int> primes;

void eulerSieve(int n) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i); // 添加素数到列表
            for (int j = 2; i * j <= n; ++j) {
                isPrime[i * j] = false; // 标记合数
                if (i % j == 0) break; // 停止内层循环
            }
        }
    }
}

int main() {
    int n;
    std::cout << "Enter the range: ";
    std::cin >> n;
    eulerSieve(n);
    std::cout << "The prime numbers within the range are:\n";
    for (int prime : primes) {
        std::cout << prime << " ";
    }
    std::cout << "\nTotal prime numbers: " << primes.size() << std::endl;
    return 0;
}

参考资料：

1. [C++实现欧拉筛法 - 风生水起 - 博客园][^1^]
2. [线性筛素数 - 欧拉筛 （包含正确性和复杂度的证明） - 学委 ...][^2^]
3. [素数筛法算法及其原理 - kentle - 博客园][^3^]
4. [6.1.1. 欧拉线性筛和欧拉函数 — C++算法编程指南 0.1 文档 ...][^4^]
5. [【算法/数论】欧拉筛法详解：过程详述、正确性证明、复杂度 ...][^9^]
6. [筛法 - OI Wiki][^10^]
7. [欧拉筛法（线性筛）的学习理解-腾讯云开发者社区-腾讯云][^11^]
8. [线性筛（欧拉筛） | Cimoc][^12^]

以上代码和原理可以帮助你理解欧拉筛的工作原理，并用C++实现统计指定区域内质数的个数。希望这对你的学习有所帮助。