Project Euler #7 Optimization

Question

I've been noticing a theme with some of the Project Euler problems. They require a huge amount of time to complete. (Problems like Largest Palindrome and 10,001st Prime) I was hoping there could be some way to optimize the code to make it better. I let this one run for over 24 minutes and it didn't finish.

public class Seven
{
    public static void main(String[] args)
    {
        //Declare Variables
        int primeCount = 0;
        int numCount = 1;
        int latestPrime = 0;

        while(primeCount <= 10001)
        {
            if(isPrime(numCount))
            {
                primeCount++;
                latestPrime = numCount;
            }
            numCount++;
        }

        System.out.println("The 10,001st prime is: " + latestPrime);
    }

    //This method will determine if a number is prime
    public static boolean isPrime(long num)
    {
        //Check for even number
        if(num % 2 == 0)
            return false;

        //Check for non-prime odd numbers
        for(long i = 3; i <= num; i += 2)
        {
            if(num % i == 0)
                return false;
        }

    //Return that the number is prime
        return true;
}

}

possible duplicate of [Why is Sieve of Eratosthenes more efficient than the simple "dumb" algorithm?](http://stackoverflow.com/questions/5649068/why-is-sieve-of-eratosthenes-more-efficient-than-the-simple-dumb-algorithm) — Sleafar, Aug 29 '15 at 06:03

score 3 · Accepted Answer · answered Aug 29 '15 at 06:00

3

You're doing a lot of repetitions, you don't need to loop through entire number in the for loop, just go until square root.

This runs in a second.

 // Check for non-prime odd numbers
      for (long i = 3; i <= Math.sqrt(num) +1; i += 2) {
         if (num % i == 0)
            return false;
      }

If you want to optimize even more, you could store prime numbers in an array and only check if the number divisible by the previous prime numbers.

answered Aug 29 '15 at 06:00

dogant

1,376
1
10
23

1

I can't believe how much faster that went. Thank you for the advice! I will be sure to keep it in the back of my head for future programs! – rsdev Aug 29 '15 at 06:06

score 1 · Answer 2 · answered Aug 29 '15 at 06:21

This program prints 10001 first prime numbers. As @Tejash Desai suggested, 2 optimizations could be done:

(1) keep the found prime numbers in a list so that tests of new primes needs to be done only on items inside this list, rather than all odd numbers; and

(2) test againts factors only up to square root of a number.

void printPrimes() {
    // Find first 10001 primes
    int p = 0;
    for (var i = 2; i <= 10001; i++) {
        p = nextPrime();
        Console.WriteLine("Prime #{0}: {1}", i, p);
    }
}

// Set of known primes
List<int> primes = new List<int>() {2};

// Find the prime next to the last one that was found
int nextPrime() {
    int k = primes[primes.Count - 1] + 1;
    while (!testPrimeUsingKnownSetOfPrimes(k)) {
        k = k + 1;
    }

    primes.Add(k);
    return k;
}

// Check if a number is prime, using the set of known primes
bool testPrimeUsingKnownSetOfPrimes(int n) {

    foreach (var p in primes) {
        // Largest prime factor of a number can't be greater than square root of the number
        if (p > Math.Sqrt(n)) {
            return true;
        }

        if (n % p == 0) {
            return false;
        }
    }

    return true;
}

PS Written in C#.

score 0 · Answer 3 · answered Aug 29 '15 at 06:05

Loop only till less than or equal to the square root of n

//Check for non-prime odd numbers for(long i = 3; i <= Math.sqrt(num); i += 2) { if(num % i == 0) return false; }

Also, another optimization would be to keep storing all the primes you've come across till now in an ArrayList and then only traverse the loop in that list.

//Check for non-prime odd numbers for(int i = 0; i <= arrayList.size(); i ++) { if(num % arrayList.get(i) == 0) return false; }             arrayList.add(num);

Project Euler #7 Optimization

3 Answers3