Project Euler #5: Smallest multiple

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?

 There's actually a really easy trick to solving this. It's not immediately obvious and I can't explain how it works well, but I'll do an example. Say we want the least common multiple of 1 through 10 (aka the smallest multiple). What we do is remove the prime factors from each of the numbers in order of smallest to lowest, but when take out a prime factor, we also remove it from any other number it can be removed from. For example

• 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• Remove 2: 1, 1, 3, 2, 5, 3, 7, 4, 9, 5
• Remove 3: 1, 1, 1, 2, 5, 1, 7, 4, 3, 5
• Remove 2: 1, 1, 1, 1, 5, 1, 7, 2, 3, 5
• Remove 5: 1, 1, 1, 1, 1, 1, 7, 2, 3, 1
• Remove 7: 1, 1, 1, 1, 1, 1, 1, 2, 3, 1
• Remove 2: 1, 1, 1, 1, 1, 1, 1, 1, 3, 1
• Remove 3: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Now we multiply all the prime factors we extracted and that's our answer! So 2 x 2 x 2 x 3 x 3x 5 x 7 = 2520 as expected. Alternatively you could've also only factored the non-prime numbers, but that would require knowing which numbers are prime - which isn't immediately obvious at high values. You could also eliminate any number which already has a multiple of itself - so 1, 2, 3, 4, and 5 - if you wanted to. An alternate version can be found here.

Coding this was pretty simple and the runtime is under 10 microseconds for numbers 1 through 20. This is probably the fastest solution I can come up with. The brute force method takes about 3 seconds in comparison.

The code can be found here.