CODEWITHSUNDEEP
javaprimes
Blaine Mucklow
Blaine Mucklow

Reputation: 591

Project Euler: Programmatic Optimization for Problem 7?

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

}

Upvotes: 3

Views: 1085

Answers (9)

the_prole
the_prole

Reputation: 8955

I simply translated the Sieve of Eratosthenes into Java. It's supposed to be one of the most efficient ways of solving for primes algorithmically. 

public static void main(String[] args){

    ArrayList<Integer> List = new ArrayList<Integer>();
    ArrayList<Integer> Primes = new ArrayList<Integer>();
    Primes.add(2);
    Integer p=2;
    Integer n=105000; 
    Integer i=1;

    while(p < n) {

        i=1;

        while((p*i)<=n) {
            List.add(p*i);
            i++;
        }

        while (p < n) {
            p++;
            if(List.contains(p)){                     }
            else                {Primes.add(p); break;}
        }

    }

    System.out.println("PRIME 10,001 is.... " + Primes.get(10000));
    // 104743

}

Upvotes: 0

Vishal
Vishal

Reputation: 11

You are better off using an int/long, and just run through loops to check if a number is prime. To optimize and accelerate your program, you could reduce iterations in the for loop by setting the limit to Math.sqrt(num).

Reference : http://www.mycoding.net/2012/01/program-to-find-10001st-prime-number-project-euler-problem-7/

Upvotes: 1

thorkia
thorkia

Reputation: 2002

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

Upvotes: 0

starblue
starblue

Reputation: 56792

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

Upvotes: 4

JRL
JRL

Reputation: 78013

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.

Upvotes: 1

Bill the Lizard
Bill the Lizard

Reputation: 405875

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.

Upvotes: 6

Craig Stuntz
Craig Stuntz

Reputation: 126557

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.

Upvotes: 0

Cine
Cine

Reputation: 4402

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.

Upvotes: 1

mob
mob

Reputation: 118635

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.

Upvotes: 13

Related Questions