埃拉托斯特尼筛法（Sieve of Eratosthenes）C++实现问题咨询

现有代码中的is_prime函数属于暴力素数判定逻辑，无需用于筛法实现。筛法核心是通过标记数组批量排除素数的倍数，时间复杂度远低于逐个判断素数的方案。

完整可运行代码 #

#include <vector>
#include <cmath>
#include <iostream>

using namespace std;

int main() {
    int n = 100;
    // 初始化标记数组，索引对应数字，值为true代表是素数，初始全部设为true，后续筛掉非素数
    vector<bool> is_prime(n + 1, true);
    // 0和1不是素数，先标记为false
    is_prime[0] = is_prime[1] = false;
    
    // 循环到sqrt(n)即可，大于sqrt(n)的数的倍数已经被更小的素数筛过
    for (int p = 2; p <= sqrt(n); p++) {
        // 如果当前p仍被标记为素数，就筛掉它的所有倍数
        if (is_prime[p]) {
            // 从p*p开始筛即可，比p*p小的倍数已经被更小的素数筛过
            for (int multiple = p * p; multiple <= n; multiple += p) {
                is_prime[multiple] = false;
            }
        }
    }
    
    // 收集所有素数
    vector<int> primes;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    
    // 输出结果验证
    cout << n << "以内的素数共有" << primes.size() << "个，分别是：" << endl;
    for (int prime : primes) {
        cout << prime << " ";
    }
    cout << endl;
    
    return 0;
}

逻辑说明 #

• 不需要单独维护整数列表、倍数列表，用布尔标记数组的索引对应数字本身，空间开销更小，操作更简便
• 外层循环终止条件设为p <= sqrt(n)即可，不需要遍历到n，因为任何大于sqrt(n)的合数，它的最小质因子一定小于等于sqrt(n)，早就被筛过了
• 筛倍数的时候从p*p开始，不需要从2*p开始，因为2p、3p这些值已经被2、3这些更小的素数筛除过了，可以减少重复操作
• 循环次数由终止条件p <= sqrt(n)自动控制，不需要额外用while循环判断终止条件，逻辑更清晰

内容的提问来源于stack exchange，提问作者jaronbass21