这是我找到我可以处理的最大质数的最好方法吗？

Question

我正在尝试找出在最大两个的乘积结束之前我可以拥有多少个素数 Long.MAX_VALUE。

需要半个多小时（和 GB 的 RAM）

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());
    }
}

编辑

我也很想知道在达到这个限制之前我得到了多少素数。所以自上而下的方法无法完成这项工作。

无论如何，我意识到我可以在我的申请中达到这两个数字，同时我会变得非常富有:)

Answer 1

应该有更快的方法来做到这一点。考虑以下因素：

对 2 和 Sqrt(Long.MAX_VALUE)
在筛法找到的最后一个素数 (last) 之后找到下一个素数 (next)。
如果 next*last 已经大于 Long.MAX_VALUE 你就完成了。
如果在next之后找不到下一个素数（我们称之为next2）
next*next2 大于 Long.MAX_VALUE

Eratosthenes 筛法的时间复杂度为 O(n*log(log(n))。

你只需要 "brute force" 2 个大于 Sqrt(Long.MAX_VALUE) 的质数。加上计算筛子所需的时间，这应该比你的方法快得多！

到了必须数素数的地步：

在计算筛子的同时数出素数的个数真的很简单！

这是我找到我可以处理的最大质数的最好方法吗？

Is this the best way I can find max prime numbers I can handle?

java

primes