### HackerRank - Project Euler #5 - Smallest Multiple

We need to find the Least Common Multiple (LCM) of all the numbers from 1 to N so as to find the smallest positive number that can be evenly divided by all the N numbers.

We first have to calculate Greatest Common Divisor (GCD) or Highest Common Factor (HCF) to calculate the LCM of all the numbers.

## What is GCD?

If we find all the prime factors of each of the numbers then multiplying the common factors gives us the GCD.
12 = 2 * 2 * 3
24 = 2 * 2 * 2 * 3
48 = 2 * 2 * 2 * 2 *3
GCD = Multiplication of common prime factors
GCD(12, 24, 48) = 2 * 2 * 3 = 12

There is another way of expressing it:
Listing all the factors
12 = 1, 2, 3, 4, 6, 12
24 = 1, 2, 3, 4, 6, 8, 12, 24
48 = 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
GCD = Pick the greatest common factor
GCD(12, 24, 48) = 12


## What is LCM?

It is the smallest positive number that is the multiple of two or more numbers.
Multiples of 30 = 30, 60, 90, 120, ...
Multiples of 45 = 45, 90, 135, 180, ...
Multiples of 15 = 15, 30, 45, 60, 75, 90, 105, ...
LCM = Least Common Multiple
LCM(30, 45, 15) = 90


## How to compute LCM?

$LCM(a, b) = \dfrac{a * b}{GCD(a, b)}$
The above relation only holds true for two numbers.
$LCM(a, b, c) \neq \dfrac{a * b * c}{GCD(a, b, c)}$
To solve this problem we need to find the LCM of N numbers. Therefore, to find the LCM of more than two numbers we need an array consisting of the numbers. But, in this case, we can do that by initializing result = 1 and then start traversing from i=2 to i=n. For each iteration we calculate, result = LCM(result, i) = (result * i) / gcd(result, i).

## My Solution in Java:

The time complexity of this code is $$O(n)$$.

It passed all the test cases on HackerRank.