Project Euler Problem 5 Solution

First posted on 17/09/2012

Question

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution in Java

boolean result = false;
int limit = 20;

// Increment by 20; because that is the highest number that is divisible by the limit
// If result is still false, it will continue looping
for (int i = limit; !result; i = i + 20) {

	for (int j = 2; j < limit; j++) {
		if (i % j == 0) {
			result = true;
		}
		else {
			result = false;
			break; // Does not continue to loop since undivisible
		}
	}
			
	// Will not evaluate if result is false
	// Looping with increment of 20
	// Until result is true for all numbers from 2 to 20
	if (result) { 
		System.out.println(i);
		break;
	}

}

Answer: 232792560 (1205 ms)

Footnotes

This is another brute-force approach I did for problem 5. I roughly drawn the algorithm on a piece of paper that looks like this:

i % j == 0
----------
1 % 1 == 0
2 % 1 == 0
3 % 1 == 0
...
i % 10 == 0
i % 10 == 0
...
i % 15 == 0 
...
i % 20 == 0

Okay that was quite straight forward I suppose. Considering i mod j returns 0, where i is the divisible number and j is 1 to 20. For loops and some if statements are needed in this case to reiterate number 1 until 20 and test all the numbers if it is divisible by it.

A big note to myself: I really need to do some huge research on the magical prime numbers and how LCM and HCF works.

I will try my best to update this solution, because it all has something to do with prime factorization and Lower Common Multipliers. Fingers crossed!