所以我会称自己为一个相当新手的程序员,因为我在学校教育中主要关注硬件,而不是很多计算机科学类(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);
}
最佳答案
由于第 10001 个质数不是那么大,您可以从使用 long
而不是 BigInteger
开始。 BigInteger
实例是一个成熟的 Java 对象,创建和操作它们的开销很大。
关于java - 欧拉计划 : Programmatic Optimization for Problem 7?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2668759/