Project Euler: Problem 5 (in Java)

Problem 5 in Project Euler is as follows:

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 by all of the numbers from 1 to 20?

As usual, I started with the brute force approach:

	int max=20;
	long candidate = 1;
	boolean success = false;
	do {
		int i;
		for (i=1; i<=max; i++) {
			if ((candidate % i) !=0) {
				//out.println(candidate + " not divisible by " + i);
				candidate=candidate+1;
				break; 
			}				
		}
		if (i>max) success = true;
	} while (!success);
	out.println("Success: " + candidate);

This is clearly a poor solution (and at ~25 seconds run time on my laptop, a very slow one).
A few improvement points:
1) The result has to be divisible by all numbers up to and including 20. So no point checking any number below 20. So we could change the starting candidate value to 20. But using the info given, we know that 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. So the solution can’t be smaller than 2520. Let’s start there.
2) Any number has to be divisible by 20, so we can increment candidate by 20 each time.
3) If a candidate is divisible by 20, it is definitely divisible by 10, so don’t even bother checking 10. If a number is divisible by 18, it is definitely devisible by 9, so don’t bother checking 9. Continue this process and we find that we only need to check if a candidate number is divisible by 11 through 19 (we are starting with a multiple of 20 and incrementing by 20 each time, so 20 as a factor is a given).
This leaves us with this slightly better solution:

	int min = 11;
	int max=19;
	long candidate = 2520;
	boolean success = false;
	do {
		int i;
		for (i=min; i<=max; i++) {
			if ((candidate % i) !=0) {
				//out.println(candidate + " not divisible by " + i);
				candidate=candidate+20;
				break; 
			}				
		}
		if (i>max) success = true;
	} while (!success);
	out.println("Success: " + candidate);

This give the same solution, but with about 400 milliseconds running time. Better, and well within the 1 minute Project Euler limit.
I submitted my solution and confirmed it was correct.
Great. But I knew my solution was still a brute force approach at heart.

As I was working through the algorithm, I began thinking about using a better starting point than 2520. For example, the smallest solution must be a number that is divisible by both 19 and 20. What is that? If I had a method that told me the lowest common multiple of 19 and 20?
As I started reading through other solutions, I began thinking more about that. If I had a function getLowestCommonMultipler(a, b)
I could apply that to the first 2 numbers (1 and 2).
Then use the result for a subsequent call, e.g. getLowestCommonMultipler(result, 3)
Then use the result for a subsequent call, e.g. getLowestCommonMultipler(result, 4)
and so on.
You would end with a solution like this

	int max=20;
	long lowestCommonMultipler = 1;
	for (int i=2; i<=max; i++) {
		lowestCommonMultipler = getLowestCommonMultipler(lowestCommonMultipler, i);			
	}
	out.println("Success: " + lowestCommonMultipler);

I admit that I had to get 'inspiration' for the implementation of the getLowestCommonMultipler() method elsewhere (see here, for example), so I won't post the implementation as it is not my own work. But identifying the need for such a method is the big breakthrough I think. The above solution ran in 6ms for me. Cool in a very geeky, Project Euler kind of way.

Tags: euler