我的C++埃拉托斯特尼筛法实现为何出现运行时错误？

核心问题及解决 #

1. 栈溢出引发运行时错误
   函数内声明的bool prime[1000006]是栈上的局部数组，在线编译器的栈空间通常远小于本地环境，大数组会直接撑爆栈内存触发错误。
   解决：改用动态分配的vector容器或者全局数组，这类内存分配在堆/静态区，空间足够。

2. 未初始化数组导致逻辑错误
   局部数组prime没有初始化，元素值是随机垃圾值，你的筛法逻辑依赖prime[p]==false判断素数，这会导致素数列表完全错误。
   解决：初始化数组所有元素为false。

3. 函数返回值不匹配
   SieveOfEratosthenes声明返回long long int，但函数内没有任何return语句，属于C++未定义行为，可能触发运行时异常。
   解决：将函数返回类型改为void。

修复后的代码 #

#include<bits/stdc++.h>
using namespace std;

vector<long long> prima;

void SieveOfEratosthenes(){
    // 用vector动态分配并初始化为false
    vector<bool> prime(1000006, false);
    for (long long int p = 2; p <= 1000000; p++) {
        if (!prime[p]){
            prima.push_back(p);
            // 处理p*p溢出的情况，避免循环变量变为负数
            for (long long int i = p * p; i <= 1000000 && i > 0; i += p){
                prime[i] = true;
            }                
        }   
    }
}     

int main(){ 
    long t;
    cin >> t;
    SieveOfEratosthenes();
    while(t--){
        long long int k;
        cin >> k;
        // 增加边界判断，防止输入的k超出预计算素数的范围
        if (k-1 < prima.size())
            cout << prima[k-1] << endl;
        else
            cout << "Invalid input" << endl;
    }
    return 0;
}

额外优化：在输出时增加边界判断，避免输入的k超过预计算的素数总数导致越界访问。

内容的提问来源于stack exchange，提问作者Delfino Jeconiah Djaja