C++埃氏筛实现输入≥46350时无输出问题求助

核心问题 #

程序在筛法上限设为46350及以上时无输出，根源在于两个致命问题：

1. 栈溢出导致程序直接崩溃 #

函数eSieve中声明的std::array<bool, num>和std::array<long long, size>是栈上分配的内存。在线编译平台的栈空间通常有限，当num增大到46350时，栈内存被占满，触发栈溢出，程序直接终止，无法执行到输出步骤。

2. 整数溢出引发逻辑混乱 #

int类型的最大值通常为2^31-1（2147483647），而46350的平方为2148322500，已经超过int的上限。在循环for(int j = i * i; j < num; j += i)中，当i足够大时，i*i会发生整数溢出变为负数，导致循环逻辑完全失效，甚至触发未定义行为。

修复后的代码 #

#include <iostream>
#include <vector>

// 筛法范围上限
const int sieve_limit = 46350;
// 素数存储的预留空间（46350以内素数约4792个，预留足够余量）
const int max_primes = 10001;

std::vector<long long> eSieve() {
    // 用vector在堆上分配内存，避免栈溢出
    std::vector<bool> numbers(sieve_limit, true);
    std::vector<long long> primes;
    primes.reserve(max_primes);

    // 初始化：0和1不是素数
    numbers[0] = numbers[1] = false;

    // 埃拉托斯特尼筛法核心逻辑
    for (long long i = 2; i * i <= sieve_limit; ++i) {
        if (numbers[i]) {
            // 用long long避免i*i溢出
            for (long long j = i * i; j < sieve_limit; j += i) {
                numbers[j] = false;
            }
        }
    }

    // 收集所有素数
    for (int i = 2; i < sieve_limit; ++i) {
        if (numbers[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

int main() {
    std::vector<long long> arr = eSieve();
    // 按实际素数数量输出，避免越界
    for (size_t i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << " ";
    }
    return 0;
}

关键修复点 #

• 替换std::array为std::vector：vector在堆上分配内存，不受栈空间限制，彻底解决栈溢出问题。
• 使用long long避免整数溢出：将循环变量i和j改为long long，确保i*i不会超过类型上限。
• 修正初始化逻辑：统一初始化所有元素为true后，手动标记0和1为非素数，逻辑更严谨。
• 安全输出素数：根据vector的实际大小输出，避免原代码固定循环次数导致的越界访问。

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