Problem 005 : Smallest Multiple

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?

                                                                                                           https://projecteuler.net/problem=5

Problem 5 is about GCD and LCM.

GCD : greatest common divisor

LCM : least common multiple

The problem already told us that 2520 is smallest number that is divisible by numbers from 1 to 10, or it is the LCM of numbers from 1 to 10.

Now we need to find LCM for 1 to 20.

Here is a simple math.

Let's say we have two integer, A and B.

And we know that G is the greatest common divisor of A and B.

Then we can write them in this way:

A = Ga

B = Gb

where a and b are relatively prime to each other.

Also, least common multiple must be divisible by both A and B but need to be as small as possible.

LCM = Gab

How do we get LCM directly from A and B?

LCM = Gab

Gab = G² ab / G = Ga * Gb / G = A * B / G

Therefore,

LCM = A * B / G

Here is recursive solution to find GCD for long a and long b:

public static long gcd(long a, long b)
{
    if (b == 0) return a;
    else return gcd(b, a%b);
}

The solution uses the Euclidean Algorithm for finding GCD:

Let's say there are two positive integer A, B A > B > 0

A = qB + R₀
B = qR₀ + R₁
R0 = qR₁ + R₂
…
R_N-1 = qR_N + 0

∴ GCD = R_N

and here is solution for LCM for integer for long a and long b:

public static long lcm(long a, long b)
{
    return a*b/gcd(a,b);
}

Answer is 232792560
Execution time is 2 ms, or 0.002 seconds
Source code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem005.java