這是我可以找到我可以處理的最大素數的最佳方式嗎？

我試圖找到有多少素數，直到最大的兩個產品超過Long.MAX_VALUE。這是我可以找到我可以處理的最大素數的最佳方式嗎？

它採取了半個多小時（和RAM GBS）

public class Main { 
    public static void main(String[] args) { 
     ArrayList <Long> primes= new ArrayList<Long>(); 
     primes.add(2L); 
     long i=3L; 
     // Looping from 3, to the limit 
     while (primes.size()<2||(primes.get(primes.size()-1)*primes.get(primes.size()-2)<Long.MAX_VALUE)) {    
      boolean isPrime = true; 
      long maxDiv =Math.round(Math.sqrt(i)); 
      int j=0; 
       while(primes.get(j)<maxDiv && isPrime) { 
       if (i % primes.get(j) == 0) { 
        isPrime = false; 
       } 
       j++; 
      }   
      if (isPrime) { 
       primes.add(i); 
       System.out.println(i); 
      } 
      i=i+2; 
     } 
     System.out.println("max size is: "+primes.size()); 
    } 
}

編輯

我也有興趣在我達到這個極限前多少素數得。所以自上而下的方法不會完成這項工作。

無論如何，我意識到，我能在我的應用程序達到這兩個數字，我會成爲富人在此期間:)

來源

2016-12-30 Igino Boffa

我不明白這個問題上的反對票。 –

我同意，因爲您做了誠實的努力並提供了代碼，所以我認爲沒有理由拒絕投票。一個負面投票應該總是通過評論來解釋（我想知道爲什麼這不是由StackOverflow強制）。重新提出您的問題，我建議您閱讀有關Erathostenes的篩網： https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes –

有人對此問題提交了近距離投票，因爲「問題要求我們推薦或找到一本書，工具，軟件庫，教程或其他非現場資源對於堆棧溢出而言是無關緊要的「。 WTF？ – samgak

應該有這樣做更快的方式地獄。考慮以下幾點：

使用篩或埃拉托色尼的數字2和Sqrt(Long.MAX_VALUE)
之間查找篩找到的最後一個素數（last）之後的下一個素數（next）。
如果next*last已經大於Long.MAX_VALUE就完成了。
如果沒有找到下一個primenumber next（可以稱之爲next2）後
next*next2是大於Long.MAX_VALUE

埃拉托色尼的篩具有O(n*log(log(n))時間複雜度。

您只需要「蠻力」的2個素數大於Sqrt(Long.MAX_VALUE)。除了計算篩子所需的時間之外，這應該比你的方法快得多！

要，你要算質數點：

這真的很容易算質數的數量，同時計算篩子！

來源

2016-12-30 10:38:25 ParkerHalo

我會試試看，當我將會結束:) –

這是我可以找到我可以處理的最大素數的最佳方式嗎？

回答

相關問題