Euler项目:问题7的编程优化？

Question

因此，我会称自己是一个相当新手的程序员，因为我主要集中在硬件在我的学校，而不是很多的计算机科学课程。

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

通过列出前六个素数: 2，3，5，7，11和13，我们可以看到第6素数是13。 10001素数是多少？

我成功地在Java中解决了这个问题，但是当我运行我的解决方案时，它花费了8秒的时间来运行。我想知道如何从编程的角度，而不是从数学的角度来优化这个问题。

数组循环和同时语句是消耗处理时间的主要内容吗？如何才能对其进行优化？同样，没有寻找一个花哨的数学equation..there，在解决方案线程中也有很多。

扰流器我的解决方案如下所示。

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

同样，尝试使用由一个稀土筛分表示的素数的BitSet，它比单独测试候选人要快得多。

Answer 3

使用ints。为您的primesList使用一个固定大小的数组，这样您就不必为内存的分配付费(或者使启动大小足够大，使您的动态列表成为一个非问题)。

使用法线来计数一个int，而计数在循环之外。