Smallest Multiple [Google Python Interview Question]

Write a function to find the smallest number that is perfectly divisible (i.e. no remainder) by all numbers from 1 to the target number.

For example, if the target value was 5, we'd return 60, because 60 is evenly divisible by 1, 2, 3, 4, and 5. There is no number smaller than 60 which satisfies this condition.

Let's start with the brute-force method, where we just blindly test all numbers, from 2 to some arbitrarily large number like a million. For each potential number, we then try to divide it by the all the numbers up to and including the target number.

If there is a remainder, we break out of the loop early and flag the number as not being perfectly divisible. If we were able to successfully divide the candidate number by all the numbers less than or equal to the target, then we've found our smallest prime and can return it!

Here's the code for the brute-force method:

Can you think of a more efficient way to solve this problem?

Hint: Do we really need to check EVERY number from 2 to a million? We know no odd number could possibly be it... because then it wouldn't be perfectly divisible by 2.

Are there other ways to prune the search space? Maybe concepts like least common multiple / greatest common denominator could help us?

Finite Upper Bound

Our above solution is naive – we just run it to a million and hope we found an answer. Can you think of an upper bound of numbers to check?

Maybe it's all the factorial questions on DataLemur, but I know the guaranteed upper bound for a perfectly divisible number $n$ is just going to be $n!$.

Looking at a target number like 6, we know the upper bound is $6! = 6 * 5 * 4 * 3 * 2 * 1 = 720$.

But wait a second... if already know our answer is divisible by 6, do we need to check if it's actually divisible by 2 or 3? Won't be definition any number that's divisible by 6 be divisible by 2 and 3 also (because 2 and 3 make up 6).