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!!
No comments:
Post a Comment
Solution for this question?