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!