这是我可以找到我可以处理的最大素数的最佳方式吗？

我试图找到有多少素数，直到最大的两个产品超过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

我会试试看，当我将会结束:) –

这是我可以找到我可以处理的最大素数的最佳方式吗？

回答

相关问题