c - 埃拉托色尼筛法错误输出

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++)

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

i当达到极限的平方根时停止筛分。

Answer 2

我认为，您错误地将内存分配给筛子。尝试：

sieve = malloc(sizeof(int)*limit + 1);

Answer 3

您可以在第一个循环中添加总和，并避免乘以可能溢出的 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);

上面的代码给了我你想要的结果。