埃拉托斯特尼筛法C++代码——内存范围错误

嘿，我看到你在实现埃拉托斯特尼筛法的C++代码时遇到了编译错误，而且代码看起来没写完（fo...那里明显是笔误）。我来帮你梳理常见问题，再给你一个能正常编译运行的完整版本！

你代码里可能存在的编译错误点 #

• 容器类型选择不当：你用了vector<int>来存储质数标记，但筛法只需要布尔值（标记某个数是否为质数），应该用vector<bool>或者vector<char>，既符合逻辑又节省内存。
• 缺少初始化操作：你提到要把所有条目初始化为true，但原代码没有做这个步骤，这会导致后续判断逻辑混乱，也可能引发未定义行为。
• 语法笔误：代码里的fo...应该是for循环的拼写错误，这是直接导致编译失败的原因之一。

修正后的完整代码 #

// sieve_of_erathosthenes.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "../../Library/std_lib_facilities.h"

int main() {
    // 创建布尔数组"prime[0..n]"并将所有条目初始化为true。
    // prime[i]最终为false表示i不是质数，否则为true
    int n = 30;
    vector<bool> prime(n + 1, true); // 初始化所有元素为true，索引从0到n

    // 0和1不是质数，先标记为false
    prime[0] = false;
    prime[1] = false;

    // 埃拉托斯特尼筛法核心逻辑
    for (int p = 2; p * p <= n; ++p) {
        // 如果prime[p]还是true，说明它是质数
        if (prime[p]) {
            // 标记p的所有倍数为非质数
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }

    // 输出所有质数
    cout << "小于等于" << n << "的质数是：" << endl;
    for (int i = 2; i <= n; ++i) {
        if (prime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

代码说明 #

• 用vector<bool> prime(n + 1, true)直接初始化了大小为n+1的布尔容器，所有元素默认是true，符合你最初的需求。
• 先手动标记0和1为非质数，因为这两个数不符合质数的定义。
• 外层循环从2开始，到sqrt(n)结束（用p*p <=n避免调用sqrt函数），内层循环标记质数的倍数为非质数，这是筛法的高效实现方式。
• 最后遍历容器，输出所有标记为true的索引，也就是质数。

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