C++埃拉托斯特尼筛法代码隐形内存错误求助：n=100万时崩溃

你的代码里有几个关键问题导致了程序崩溃，咱们一步步拆解解决：

1. 数组越界访问（最直接的崩溃原因） #

你创建的vector<bool> arr(n, true)大小为n，合法索引范围是0到n-1，但内层循环的条件是j <= n——当j等于n时，arr[j]会访问超出容器范围的内存，这属于未定义行为，直接触发崩溃。

解决方法很简单：把vector的大小调整为n+1，这样就能容纳从0到n的所有数：

vector<bool> arr(n + 1, true);

2. 循环条件的严谨性优化 #

外层循环的i * i < n会漏掉i等于sqrt(n)的情况（比如n=100时，i=10不会进入循环）。虽然这不会导致错误（10的倍数已经被2、5标记过），但改成i * i <= n更符合埃氏筛的逻辑，也避免边界歧义：

for(i = 2; i * i <= n; i++){

额外建议：替换vector（规避潜在实现问题） #

vector<bool>是C++里特殊的位压缩容器，虽然内存占用极小，但部分编译器的实现可能存在奇怪的兼容性问题。如果调整后仍有崩溃，可以换成vector<char>或vector<int>，内存开销分别是1MB（1e6字节）和4MB（1e6*4字节），对于现代电脑来说完全无压力：

vector<char> arr(n + 1, true);

修改后的完整代码 #

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

int main(){
    long n = 1000000, i, j;
    vector<bool> arr(n + 1, true); 
    arr[0] = arr[1] = false; // 标记0和1不是质数
    
    for(i = 2; i * i <= n; i++){
        if(arr[i]){
            for(j = i * i; j <= n; j += i){ // 从i*i开始更高效，避免重复标记
                arr[j] = false;
            }
        }
    }
    
    cout << "Made it here." << endl;
    // 若需要输出质数，可添加以下代码
    // for(i=2; i<=n; i++){
    //     if(arr[i]) cout << i << " ";
    // }
    return 0;
}

内层循环从i*i开始而非i+i是个小优化——i*2、i*3…i*(i-1)已经被更小的质数标记过，无需重复操作。

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