2

我正在使用eratosthenes的筛子编写一个素数生成器。我已经让它生成低于 521102 的素数，但任何更高的数字都会导致程序崩溃。这是我的代码。

#include <iostream>
using namespace std;

int main ()
{
    int long MAX_NUM = 1000000;
    int long MAX_NUM_ARRAY = MAX_NUM+1;
    int Num_Array [MAX_NUM_ARRAY];
    std::fill_n(Num_Array, MAX_NUM_ARRAY, 3);
    int long sieve_prime = 2;
    int long sieve_prime_constant = 0;
    Num_Array [0] = 1;
    Num_Array [1] = 1;



    while (sieve_prime_constant <= MAX_NUM_ARRAY)
    {
        if (Num_Array [sieve_prime_constant] == 1)  
        {

            sieve_prime_constant++;
        }

        else
        {
        Num_Array [sieve_prime_constant] = 0;  
        sieve_prime=sieve_prime_constant; 
            while (sieve_prime<=MAX_NUM_ARRAY - sieve_prime_constant)  
            {
                sieve_prime = sieve_prime + sieve_prime_constant;
                Num_Array [sieve_prime] = 1;
            }

            if (sieve_prime_constant <= MAX_NUM_ARRAY)
            {
                sieve_prime_constant++;
                sieve_prime = sieve_prime_constant;
            }
        }
    } 
return 0;
}

我将 MAX_NUM 设置为 1000000，但它不起作用。但正如我之前所说，低于 521102 的数字确实有效。我需要能够测试更高的数字。我的问题是什么，我该如何解决？

非常感谢！

感谢您的回复。我尝试了动态分配数组的解决方案。在某种程度上，它运作良好。将 MAX_NUM 设置为 5 亿左右后，我在运行程序时收到此错误...

在抛出 'std::bad_alloc' what() 的实例后调用终止：std::bad_alloc

此应用程序已请求运行时以不寻常的方式终止它。请联系应用程序的支持团队以获取更多信息。

拥有 5 亿的屋顶已经接近可接受，但更高还是更好？还有其他想法吗？

4

3 回答 3

3

假设您在 Windows 上，您的堆栈太小（默认为 1MB），无法在堆栈帧中容纳以下变量：

int Num_Array [MAX_NUM_ARRAY];

您应该在堆中分配它：

int *Num_Array = new int[MAX_NUM_ARRAY];
...
delete[] Num_Array;
于 2013-02-10T17:42:42.093 回答
1

也许是因为你正在破坏堆栈。将数组移出main()函数怎么样？

#define MAX_NUM = 1000000;
#define MAX_NUM_ARRAY (MAX_NUM + 1)
int Num_Array[MAX_NUM_ARRAY];

int main()
{
    // etc.
    return 0;
}
于 2013-02-10T17:42:26.147 回答
0

The fact that you're using std::fill_n indicates you're actually writing C++, not C.

You can drastically reduce the memory consumption of your program by using a real bool array instead of an int array. Since you're using C++, you can get a Boolean array using std::vector<bool>. Unlike bool[n], std::vector<bool>(n) only takes up n bits (bool[n] takes up maybe 8n bits, or whatever the smallest alignment is on your machine/compiler, and your Num_Array[n] actually takes up 32n bits since you're using 32-bit integers to store Boolean values).

The other comments suggest you store this value on the heap instead of on the stack. std::vector<bool> will do that for you automatically.

于 2013-02-10T17:45:23.663 回答