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!

Show Comments

Get the latest posts delivered right to your inbox.