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?
The brute force way is to increment from 1 to a billion (or any big number) and for each one of those numbers test it for even divisibility by 1 to 20. I'm trying to think of clever non-brute-force ways, but the best I can do is reduce the need for some of the numbers to divide by. Everything is divisible evenly by 1 so there's no need to check for that. If I'm checking for divisibility by 9 then checking for 3 isn't necessary. Is there a pattern here that I'm missing?
Maybe if I go backwards: If a number is divisible by 20 then it's assumed that it's also divisible by 10, 5, and 2. 19 needs to be checked. 18 is divisible by 2 and 6... Ok maybe the trick is that I only need to check for divisibility the numbers that aren't already evenly divisible by other numbers in the 1-20. There has to be a more graceful way of saying that. The point is I can reduce the 20 checks per number.. So...(scribbling on paper here)... I should only have to check from 11-20. That's better, I guess? 10 is covered by the check of 20, 9 by 18, 8 by 16, etc.
Energy permitting I'll try to bang this out in C tonight.
No comments:
Post a Comment