c - Eratosthenes 筛法错误输出

Question

我试图找出所有素数的总和，最多为 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。

你能告诉我哪里出了问题吗？我想不通。

Answer 1

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

对于 i > 65535，计算 j*i 溢出。在这种情况下，这会虚假地产生一些伪复合 Material 。

当 i 达到限制的平方根时停止筛选。