2

私は今日、休憩時間に忙しくするために Project Euler の問題に取り組み始めました。問題の 1 つは、200 万未満のすべての素数の合計を求めているため、エラトステネスのふるいを一緒に投げて、それらすべての数を見つけました。 

unsigned long i, j, sum = 0, limit = 2000000;

// Allocate an array to store the state of numbers (1 is prime, 0 is not).
int* primes = malloc(limit * sizeof(int));

// Initialize every number as prime.
for (i = 0; i < limit; i++)
    primes[i] = 1;

// Use the sieve to check off values that are not prime.
for (i = 2; i*i < limit; i++)
    if (primes[i] != 0)
        for (j = 2; i*j < limit; j++)
            primes[i*j] = 0;

// Get the sum of all numbers still marked prime.
for (i = 2; i < limit; i++)
    if (primes[i] != 0)
        sum += i;

printf("%d", sum);

limitこれは、約50万まで完全に機能します。この後、ランダムな値が返されます (たとえば、1000000 は -1104303641 を返します)。unsigned longすべての変数をunsigned long long無駄に宣言しようとしました。primes[]その時点で 1 と 0 しか含まれていないため、エラーは最後の 4 行で発生しているようです。これは、処理されている値のサイズと関係があると思いますが、誰かガイダンスを提供できますか?

4

2 に答える 2

6

Wolfram Alpha によると、500000 未満の素数の合計は9914236195です。

その数値は 32 ビット整数に収まらないため、合計ループ中に int をオーバーフローさせています。を使用することもできますがuint64_t、その問題は最終的に十分に高い制限で再び発生します (ただし、2000000 の制限が適合すると思われます)。

于 2012-12-11T04:00:41.637 に答える