java - 欧拉计划 : Programmatic Optimization for Problem 7?

Question

所以我会称自己为一个相当新手的程序员，因为我在学校教育中主要关注硬件，而不是很多计算机科学类(class)。

所以我解决了Project Euler的问题7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

我设法在 Java 中毫无问题地解决了这个问题，但是当我运行我的解决方案时，它需要 8 秒才能运行。我想知道如何从编程的角度而不是数学的角度对其进行优化。

数组循环和 while 语句是消耗处理时间的主要因素吗？以及如何对其进行优化？再次不是在寻找一个奇特的数学方程式。在解决方案线程中有很多这样的东西。

剧透下面列出了我的解决方案。

public class PrimeNumberList {

private ArrayList<BigInteger> primesList = new ArrayList<BigInteger>();

public void fillList(int numberOfPrimes) {
    primesList.add(new BigInteger("2"));
    primesList.add(new BigInteger("3"));
    while (primesList.size() < numberOfPrimes){
        getNextPrime();
    }
}

private void getNextPrime() {
    BigInteger lastPrime = primesList.get(primesList.size()-1);
    BigInteger currentTestNumber = lastPrime;
    BigInteger modulusResult;
    boolean prime = false;
    while(!prime){
        prime = true;
        currentTestNumber = currentTestNumber.add(new BigInteger("2"));
        for (BigInteger bi : primesList){
            modulusResult = currentTestNumber.mod(bi);
            if (modulusResult.equals(BigInteger.ZERO)){
                prime = false;
                break;
            }
        }
        if(prime){
            primesList.add(currentTestNumber);
        }
    }
}

public BigInteger get(int primeTerm) {
    return primesList.get(primeTerm - 1);
}

Answer 1

由于第 10001 个质数不是那么大，您可以从使用 long 而不是 BigInteger 开始。 BigInteger 实例是一个成熟的 Java 对象，创建和操作它们的开销很大。