2

エラトステネスのふるいを使用して素数のジェネレーターを作成しています。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

あなたが使用しているという事実は、std::fill_nあなたが実際に C ではなく C++ を書いていることを示しています。

int 配列の代わりに実数 bool 配列を使用すると、プログラムのメモリ消費を大幅に削減できます。C++ を使用しているため、 を使用してブール配列を取得できますstd::vector<bool>。とは異なりbool[n]、std::vector<bool>(n)n ビットのみを使用します (bool[n]おそらく 8n ビット、またはマシン/コンパイラで最小のアライメントが必要であり、Num_Array[n]ブール値を格納するために 32 ビット整数を使用しているため、実際には 32n ビットを使用します)。

他のコメントは、この値をスタックではなくヒープに保存することを提案しています。std::vector<bool>自動的にそれを行います。

于 2013-02-10T17:45:23.663 に答える