Puzzle 33 – Solution

A number is Prime if it there is no number that can divide it completely except 1 and itself. However to check if a number is prime it is not necessary to check all the way up to (number-1). It is sufficient that there it has no factor less than or equal to its square root. (Pretty easy to prove - try it!).

My optimization – Just add a Math.sqrt() at line 10 and the code runs in less than 5 seconds compared to the 30 minutes or so it takes without the optimization! Woo thats what I call an optimization!!!

package com.sam.twisters.euler;
/*
* The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
* Find the sum of all the primes below two million.
*/
public class Proj10 {

public static boolean isPrime(long n){
   boolean isPrime = true && (n==2 || n%2!=0);
//Optimized-->for(long i=3; i<n&&isPrime;i+=2){ 14 chars added
        for(long i=3; i<Math.sqrt(n)+1&&isPrime;i+=2){
       if(n%i ==0){
           isPrime = false;
       }
   }
   return isPrime;
}

public static void main(String[] args) {
   long startTime = System.nanoTime();

   long sum = 0;
   int n=2;
   do{
       if(isPrime(n)){sum+=n;}
       n++;
   }while(n < 2000000);
   System.out.println(sum);

   long estimatedTime = System.nanoTime() - startTime;
   System.out.println((float)estimatedTime/1000000000);
}
}

http://www.blogtrog.com/code.aspx?id=dc704a56-8ea9-4726-85e4-b2e94e44e18e

A lot of folks came up with a similar conceptual answer and a few more suggestions. You can have a look at all the solution in the previous post.

Leaders board to be updated during the weekend!!