Here is the optimization that I had in mind. It makes the code run in less than 5 seconds on my machine. Throw in a couple of more optimizations like incrementing by 20 instead of 1 (see comments here) brings down the execution time to less than half a second!!

package com.sam.twisters.euler;

/* Problem 5 : Euler

* 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

* What is the smallest number that is evenly divisible (divisible without reminder) by all of the numbers from 1 to 20?

*/

public class prog5 {

/*Simple function to check if the divisor completely divides the divident*/

public static boolean isDivisble(int divident, int divisor) {

if(divident%divisor == 0){

return true;

}

else{

return false;

}

}

public static void main(String[] args)

{

long startTime = System.nanoTime();

boolean va = true;

/* Start looping though all the numbers and see if we can find one divisible by all numbers

* from 1 to 20.

*/

int i = 1;

do{

va = true; //Assume that i is a valid answer to the puzzle

//Optimization -->for(int d=1;d<=20;d++){

/*(1 char, start from 11 and not 1).

This works since atleast one of the numbers from 11 to 20 has each of the numbers 1-10 as a factor,

so for example when we test if a number is divisble by 12 - we also indirectly test that the

number is divisible by 2,3,4 and 6

*/

for(int d=11;d<=20;d++){

if (!isDivisble(i, d)){ //Yikes my assumption was wrong!

va = false;

//Optimization -->break; (6 char)

break;

}

}

i++;

}while(!va);

System.out.println(i);

long estimatedTime = System.nanoTime() - startTime;

System.out.println((float)estimatedTime/1000000000);

}

}

http://www.blogtrog.com/code.aspx?id=7617cc6e-c724-4122-b5c5-bf6eb703a700

Best solutions for the week?

@TheMalkolm - I'll pick TheMalkolm solution - its a pretty good optimization to the existing code.

@Sebastian - Yep your second solution is pretty neat (took some time figuring out how it works!!) though as you pointed out it uses a completely different algorithm. Neat nonetheless!!

## No comments:

## Post a Comment

Solution for this question?