C++ Sieve of Eratosthenes算法导致堆栈溢出

Question

我正在研究一个简单的埃拉托色尼筛法算法，代码如下:

int main()
{

    const int n = 1000000;

    int sqrn = floor(sqrt(n));

    bool primes[n + 1] = { 0 }; // false means prime, true not prime

    primes[0] = true;
    primes[1] = true;

    for (int i = 2; i <= sqrn; i++){

        if (primes[i] == false) {
            int j = i + i;
            while (j<=n-1){
                primes[j] = true;
                j = j + i;
            }
        }
    }
}

我的主要问题是，如果我尝试将搜索数组设置为大于 n=1000000，此代码会导致堆栈溢出错误。我不确定这是因为编程错误还是因为程序无法容纳大于 10^6 条目的 bool 数组？任何建议表示赞赏。

我的另一个小问题是，在 for 循环语句之外设置 n 的平方根的计算是否可以提高执行速度。

谢谢

Answer 1

您正在堆栈上分配 primes 数组。堆栈只有有限的大小(它相当大，但仍然有限)。您可以:

• 在全局数据区分配你的数组，或者
• 使用 new 在堆上分配数组