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

計算j*i溢出爲i > 65535。在這種情況下，這會虛假地產生一些僞複合材料。

當i達到極限的平方根時停止篩分。

Answer 2

我想，你錯誤地malloc內存篩。 嘗試：

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

Answer 3

您可以添加到款項在第一循環，避免乘我* j，它可能溢出。 還分配空間限制+ 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); 

上面的代碼給我你想要的結果。