使用大數字的Eratosthenes算法Java Sieve時出現奇怪的數值錯誤？

我遇到了最奇怪的問題，並且一直在進行可怕的調試。我想我會在這裏發表意見。使用大數字的Eratosthenes算法Java Sieve時出現奇怪的數值錯誤？

public static void sieve(int limit) { 

    for (int i = 2; i < limit; i ++) { 

     if (mPrimes[i] == true) { 

      for (int j = i*i; ((j < limit) && (j > 0)); j += i) { 
       mPrimes[j] = false; 
      } 

     } 

    } 

}

（假設mPrimes都是最初真）

這裏的漁獲：

當我運行此程序的10限額，100，1000，10000，甚至是100000，它報告計數正確的數字低於給定的數字，作爲與本頁面交叉引用：http://primes.utm.edu/howmany.shtml

但是，當我運行的參數1000000（一百萬），我得到一個結果是正好7離正確價值（它報告78491英寸tead of 78498）。

此外，我在本程序中實施的所有其他素數計數方法都報告了正確的值。

這裏是真正的陷阱：如果我有

i+i

至於開始直接從種子值「劃掉」，而不是從廣場開始取代

i*i

（這是我的教授在他的示例代碼中所做的），它的工作原理。

這讓我只能假設當我非常大時，廣場上發生了一些奇怪的事情。

有什麼建議嗎？

來源

2012-01-28 cemulate

你試過使用long而不是int嗎？ http://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html – 2012-01-28 06:18:41

沒有理由在你的第二個陳述中加入'j> 0'。由於j是i的平方，它總是大於0，所以j總是大於0. – 2012-01-28 21:25:18

是的，這實際上是因爲相同錯誤而導致的先前修復（i * i溢出並創建-2^31，仍然是通過了<極限測試）。我可以刪除，現在我已經修復了問題 – cemulate 2012-01-29 07:28:09

其溢出錯誤。 1,000,000 * 1,000,000需要比int更多的位（2 * 32 - 1）可容納的位數。您需要使用很長的（2 * 64 -1）。

來源

2012-01-28 06:22:00

當然。非常有意義。這確實解決了它，所以謝謝！ – cemulate 2012-01-28 06:48:12

另外，爲了避免溢出，外循環可以是這樣的：for (int i = 2; i*i < limit; i++)，這將是更快（導致limit下的任何非質數必須至少有一個素因子sqrt(limit)下）

來源

2012-01-28 06:37:39 OleGG

有如果i*i超出限制，則沒有意見可以跨越任何數字。因此，如果i超過此限制，則不必使用長整數，而只需將變量strike_limit初始化爲sqrt(i)的上限，甚至不嘗試輸入刪除循環。對不起，我不太清楚Java是否足夠編寫代碼，但這應該是

int strike_limit =（int）（sqrt（（double）limit）+ 0.5）的效果。

if (mPrimes[i] && i < strike_limit) { 
     for (int j = i*i; j < limit; j += i) { 
      mPrimes[j] = false; 
     } 
    }

這可以保證你在計算i²時不會溢出。小心分析轉角情況。

來源

2012-01-28 10:30:30 kkm

變量i最初是2並且在每一步都增加，所以它總是正數。可變Ĵ最初我 × 我，它是正的，並且由正數我在每一步，所以Ĵ增加始終爲正。爲什麼在內循環中測試j> 0？

來源

2012-01-29 01:23:10 user448810

使用大數字的Eratosthenes算法Java Sieve時出現奇怪的數值錯誤？

回答

相關問題