Problem 005


Project Euler

Smallest multiple

Problem 5

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?


Looping from 20 to 2, a running product of the number is kept and checked against the next number to find the greatest common divider (gcd) between them. If the gcd is not equal 1, the next number is divided by the gcd before multiplied into the running product. For example, when the running product is 20×19 and the next number is 18, the gcd between them is 2, so the next running product should be 20x19x9 and so on. Also notice that once the loop get pass 11, any number at and below 10 will not affect the outcome of the result because all of them is equal to the gcd a number above 11 and themselves.

Advertisements