0

私は200万までのすべての素数の合計を見つけようとしていました.

そこで、次のコードを書きました。

#include <math.h>
#include <stdlib.h>
#define limit 2000000
int main(void)
{
    unsigned int *sieve, i, j;
    unsigned long long int sum = 0;
    sieve = malloc(sizeof(int)*limit);
    for(i=2;i<=limit;i++)
        sieve[i] = 1;
    for(i=2;i<=limit;i++)
    {
        if(sieve[i])
        {
            for(j=i;j*i<=limit;j++)
                sieve[j*i] = 0;
        }
    }

    for(i=2;i<=limit;i++)
{
        if(sieve[i])
            sum += i;
    }
    printf("The sum is %llu\n",sum);
    return 0;
}

答えは のはずですが142913828922、取得してい142889228620ます。

何が問題なのか教えていただけますか？私はそれを理解することはできません。

4

3 に答える 3

3 
unsigned int *sieve, i, j;
for(j=i;j*i<=limit;j++)

の計算j*iがオーバーフローしi > 65535ます。この場合、それは偽りにいくつかの疑似コンポジットを生成します。

i限界の平方根に達したら、ふるい分けを停止します。

于 2012-09-06T15:47:36.573 に答える
3

私は、ふるいのために間違ってメモリを割り当てていると思います。試す：

sieve = malloc(sizeof(int)*limit + 1);
于 2012-09-06T15:50:19.203 に答える
2

最初のループで合計に加算し、オーバーフローする可能性のあるi*jの乗算を回避できます。また、limit+1アイテム用のスペースを割り当てます。

for(i=2;i<=limit;i++)
{
    if(sieve[i])
    {
        // Add to sum
        sum += i;
        // Zero all multiples of i, up to limit
        for(j=i; j <= limit; j+=i)
            sieve[j] = 0;
    }
}
printf("The sum is %llu\n",sum);

上記のコードはあなたが望む結果を私に与えます。

于 2012-09-06T15:53:02.707 に答える