Project Euler : Smallest Multiple

Problem Statement :

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?

This is basically finding the LCM of first 20 natural numbers.

Method 1:

Brute force method would be to go in a loop 

check if the number is divisible by all 20 numbers (using if else statements ) otherwise increase the number and  repeat till you find the answer.

Method 2:

Find the LCM the normal way.

Let x be divisible by any number less than all numbers less than 20.

Any number can be represented as a product of all prime numbers (raised to powers) less than itself. So, any number < 20 can represent as a product of prime numbers less than 20.

x =  2pow(k1)*3pow(k2)*5pow(k3)*7pow(k4)*11pow(k5)*13pow(k6)*17pow(k7)*19pow(k8)

k1, k2, k3... such that they are equal to the highest power used with the corresponding prime while representing any number less than 20.

for 2:
the highest value of k1 would be 4 for 16 = 2^4;

for 3:

the highest value of k2 would be 2 for 9 = 3^2;

for 5 or other primes > 5:

the highest value of k3,k4.... would be 1 as  5^2 =25 > 20;

so x = 2^4*3^2*5*7*11*13*17*19 = 232792560;

.