一千萬個為什麽

搜索

項目Euler:問題7的程序化優化?

所以我稱自己是一個相當新手的程序員,因為我主要關註我學校的硬件,而不是很多計算機科學課程。

所以我解決了Euler項目的問題7:

通過列出前六個素數:2,3,5,7,11和13,我們可以看到第6個素數是13。

     

第10001個素數是多少?

我設法在Java中沒有問題地解決了這個問題,但是當我運行我的解決方案時,它花費了8並且改變了運行時間。我想知道如何從編程的角度優化這一點,而不是數學觀點。

數組循環和while語句主要是耗費處理時間嗎?這怎麽可以優化?再一次不尋找一個花哨的數學方程式......在解決方案線程中有很多。

SPOILER My solution is listed below.

public class PrimeNumberList {

private ArrayList primesList = new ArrayList();

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

}

最佳答案

由於第10001個素數不是那麽大,您可以先使用 long 而不是 BigIntegerBigInteger 實例是一個成熟的Java對象,在創建和操作它們時會有很多開銷。

轉載註明原文: 項目Euler:問題7的程序化優化?