CODEWITHSUNDEEP
javaoptimization
rsdev
rsdev

Reputation: 140

Project Euler #7 Optimization

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

}

Upvotes: 1

Views: 186

Answers (3)

Khanh Nguyen
Khanh Nguyen

Reputation: 11134

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#.

Upvotes: 1

Tejash Desai
Tejash Desai

Reputation: 466

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

Upvotes: 0

dogant
dogant

Reputation: 1386

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.

Upvotes: 3

Related Questions