Prime Generator溢出？ C++

我正在爲使用eratosthenes篩的質數編寫一個生成器。我已經得到它在521102以下產生質數，但任何更高的數字都會導致程序崩潰。這是我的代碼。Prime Generator溢出？ C++

#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的」實例以後有什麼（）的std :: bad_alloc的

此應用程序已經要求運行時以不尋常的方式終止它。有關更多信息，請聯繫應用程序的支持團隊。

擁有500萬的屋頂接近可接受的水平，但更高的水平仍然會更好？有沒有其他想法？

來源

2013-02-10 Nathan J

哪一行確切導致崩潰？ – 2013-02-10 17:40:37

您可能正在Windows上運行，可能超過堆棧的最大限制。要麼動態分配數組，要麼靜態分配（可能在函數之外）或找到增加堆棧大小的方法。 – 2013-02-10 17:42:53

這不是問題，但使用長整數的習慣用法是將它們簡單地聲明爲「long」。 – 2013-02-10 19:49:22

也許是因爲你在粉碎堆棧。如何將陣列移出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-10 17:42:26

去報復downvotes！ – 2013-02-10 18:27:55

假設你使用的是Windows，你的籌碼是太小（默認爲1MB），以適應在棧幀以下變量：

int Num_Array [MAX_NUM_ARRAY];

你應該在分配它堆：

int *Num_Array = new int[MAX_NUM_ARRAY]; 
... 
delete[] Num_Array;

來源

2013-02-10 17:42:42 JosephH

「你應該在堆中分配它。」 - 爲什麼？是不是（未）初始化的內存（數據或BSS）足夠好？ – 2013-02-10 17:43:56

@ H2CO3糾正我，如果我錯了，但我認爲這隻會不必要地增加可執行文件的大小？ – JosephH 2013-02-10 17:46:58

如果你有一些過早優化戰爭的胃口：爲什麼不呢？那麼它可能會增加可執行文件的大小，但它也會更快，因爲它有一個不變的地址。 – 2013-02-10 17:48:56

您使用std::fill_n表明你實際上寫C++，不C.事實

通過使用實數布爾數組而不是int數組，可以大大減少程序的內存消耗。由於您使用的是C++，因此您可以使用std::vector<bool>來獲得布爾數組。與bool[n]不同，std::vector<bool>(n)只佔用n位（bool[n]佔用8n位，或者機器/編譯器的最小對齊方式，而Num_Array[n]實際佔用32n位，因爲您使用32位整數存儲布爾值）。

其他評論建議您將此值存儲在堆而不是堆棧中。 std::vector<bool>會自動爲你做。

來源

2013-02-10 17:45:23 Zach

我的程序編寫的方式是在數組中使用三個變量。一個是任意的，所以我可以看到布爾數組背後的邏輯。但是，我將如何實現這一點，以便其他任意變量仍可以包含在內？ - 謝謝 – 2013-02-10 18:25:37

看看你的代碼，它看起來像你檢查或設置的唯一值是0或1.因爲檢查1後，你的代碼將它設置爲0（不檢查3），我認爲它會有如果您將整個數組初始化爲0而不是3，則效果相同。然後，您可以將所有內容存儲爲單個位。 – Zach 2013-02-10 19:38:27

Prime Generator溢出？ C++

回答

相關問題