Wednesday, June 17, 2009

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){
= false;
return isPrime;

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

long sum = 0;
int n=2;
while(n < 2000000);

long estimatedTime = System.nanoTime() - startTime;

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?