Project Euler: Programmatic Optimization for Problem 7?

Question

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

}

Answer 1

Since the 10001st prime number is not that big, you could start by using long instead of BigInteger. A BigInteger instance is a full-fledged Java Object and there is a lot of overhead in creating and manipulating them.

Answer 2

You can benchmark it for yourself, but I'd guess that the for (BigInteger bi : primesList) loop is where you're spending most of your time. You're looping through the entire list of primes. You can break out of that loop as soon as you reach a prime candidate divisor that's greater than the square root of the number you're testing for primality.

Another (very slight by comparison) improvement will be in caching new BigInteger("2") and reusing it instead of creating a new BigInteger with the same value each time through your while loop. <-- Still a good practice, but it's less significant than rounding error in this case.

Answer 3

Use ints. Use a fixed size array for your primesList, so that you don't have to pay for allocation of memory (or make the start size big enough for your dynamic list to make it a non-issue).

Use a normal for that counts an int instead, with the Count being outside the loop.

Answer 4

I notice your code tests all candidates for divisibility by two. But your prime candidates are never even. So you can skip this first test. It's a small thing, but you'll save 9999 mods.

Answer 5

Since you're looping on while(!prime) in getNextPrime(), it's guaranteed to return a prime, so you could change your loop in fillList without calling size() each time. Probably not much of a gain, but it kinda doesn't make sense to calculate the size each time when you know it's being incremented by 1.

Also, you could try with a LinkedList instead of an ArrayList. In this particular use case, it could actually be faster.

Answer 6

Also try the Sieve of Erathostenes with the primes represented by a BitSet, it is much faster than testing candidates separately.

Answer 7

Here is a .NET solution... My tests indicated that I received the 10001st prime in 132ms, and 100,000 prime in 4417ms.

public static IEnumerable<long> GetPrimes(int numberPrimes)
{
  List<long> primes = new List<long> { 1, 2, 3 };
  long startTest = 3;

  while (primes.Count() < numberPrimes)
  {
    startTest += 2;
    bool prime = true;
    for (int pos = 2; pos < primes.Count() && primes[pos] < Math.Sqrt(startTest); pos++)
    {
      if (startTest % primes[pos] == 0)
      {
        prime = false;
      }
    }
    if (prime)
      primes.Add(startTest);
  }
  return primes;
}