项目欧拉:问题7的程序化优化？

Question

所以我称自己是一个相当新手的程序员,因为我主要关注我学校的硬件而不是很多计算机科学课程.

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

通过列出前六个素数:2,3,5,7,11和13,我们可以看到第6个素数是13.

什么是第10001个素数？

我设法在没有问题的情况下在Java中解决了这个问题,但是当我运行我的解决方案时,它花费了8并且更改了秒数.我想知道如何从编程的角度优化这一点,而不是数学观点.

数组循环和while语句主要是耗费处理时间吗？这怎么可以优化？再一次不寻找一个奇特的数学方程式......在解决方案线程中有很多.

SPOILER我的解决方案如下.

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对象并且在创建和操作他们大量的开销.

Answer 2

您可以自己对它进行基准测试,但我猜测for (BigInteger bi : primesList)循环是您花费大部分时间的地方.你循环遍历整个素数列表.一旦你达到一个主要的候选除数,你就可以突破那个循环,这个除数大于你正在测试素数的平方根.

另一个(通过比较非常轻微)改进将在缓存new BigInteger("2")和重用它,而不是BigInteger每次通过while循环创建具有相同值的新.< - 仍然是一种很好的做法,但在这种情况下,它不如舍入误差重要.