3

200 万未満のすべての素数の合計を返すプログラムを作成しました。これで何が起こっているのか本当にわかりません。正解が142913828922の場合、答えとして142891895587が得られます。そこにいくつかの素数が欠けているようです。getPrime 関数が想定どおりに機能すると確信しています。以前に数回使用しましたが、正常に動作しました。コードは次のとおりです。

vector<int> getPrimes(int number);

int main()
{

    unsigned long int sum = 0;
    vector<int> primes = getPrimes(2000000);

    for(int i = 0; i < primes.size(); i++)
    {
        sum += primes[i];
    }

    cout << sum;

    return 0;
}


vector<int> getPrimes(int number)
{

    vector<bool> sieve(number+1,false);
    vector<int> primes;
    sieve[0] = true;
    sieve[1] = true;

    for(int i = 2; i <= number; i++)
    {
        if(sieve[i]==false)
        {
            primes.push_back(i);
            unsigned long int temp = i*i;
            while(temp <= number)
            {
                sieve[temp] = true;
                temp = temp + i;
            }
        }
    }
    return primes;
}
4

5 に答える 5

10

がであるため、式i*iがオーバーフローします。に割り当てられる前に切り捨てられます。オーバーフローを回避するには、次のようにキャストします。iinttempstatic_cast<unsigned long>( i ) * i

さらに良いことに、その条件が発生する前に反復を終了します: for(int i = 2; i*i <= number; i++).

テスト済み。

ちなみに、これが余分な素数を生成しないだけでなく、いくつかの素数を欠落させないのはちょっと（不）幸運です。int値は署名されており、オーバーフロー時に負になる可能性があり、§4.7/2 を読むと、スキップする内側のループ。

于 2010-05-10T04:44:41.920 に答える
2

データ型の制限に達している可能性があります: http://en.wikipedia.org/wiki/Long_integer。

于 2010-05-10T04:19:21.500 に答える
1

この行が問題です：

unsigned long int temp = i*i;
于 2010-05-10T04:38:30.273 に答える
0

プラットフォームには64ビット長が必要です。この行：

unsigned long int temp = i * i;

iがintとして宣言され、乗算結果もint（32ビット）であるため、は正しく計算されません。乗算を強制的に長くします。

unsigned long int temp = (unsigned long int) i * i;

私のシステムでは、longは32ビットなので、両方を変更tempするsum必要がありunsigned long longました。

于 2010-05-10T06:00:41.013 に答える
0

ヒントをあげます。に与える初期値をよく見てくださいtemp。から除外する最初の値は何sieveですか? i除外する必要がある他の小さな倍数はありますか? 適切な数値がすべてスキップされるようにするには、どの初期値を使用できますか?

これを自分で理解するのに役立ついくつかのテクニックがあります。1 つは、より低い制限を使用してプログラムを動作させることです。200 万の代わりに、たとえば 30 を試してみてください。これは十分に小さいので、正しい答えを手ですばやく計算でき、一度に 1 行ずつ紙の上でプログラムを実行することさえできます。これにより、どこで問題が発生し始めているかを発見できます。

もう 1 つのオプションは、デバッガーを使用してプログラムを 1 行ずつウォークスルーすることです。デバッガーは強力なツールですが、習得が必ずしも容易ではありません。

デバッガーを使用してプログラムをトレースする代わりに、プログラムの進行に応じてメッセージを出力できます。getPrimesたとえば、合計を出力するだけでなく、結果の各数値を出力するようにします。(これが、最初に下限を試してみたいもう 1 つの理由です。出力量に圧倒されないようにするためです。)

于 2010-05-10T04:48:08.653 に答える