Project Euler: Programmatic Optimization for Problem 7?
- by bmucklow
So I would call myself a fairly novice programmer as I focused mostly on hardware in my schooling and not a lot of Computer Science courses.
So I solved Problem 7 of Project Euler:
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?
I managed to solve this without problem in Java, but when I ran my solution it took 8 and change seconds to run. I was wondering how this could be optimized from a programming standpoint, not a mathematical standpoint.
Is the array looping and while statements the main things eating up processing time? And how could this be optimized? Again not looking for a fancy mathematical equation..there are plenty of those in the solution thread.
SPOILER My solution is listed below.
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);
}
}
