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 seems easy, isn't it?
Basically this is a problem of finding the least common multiple - LCM(1,2,3,...,20);
1) BRRRRRRUTE-FORCE ALL THE DAY:
Since LCM(a,b,c) = LCM( LCM(a,b), c), so we can compute the LCM binaurally.
To compute the LCM(a,b): loop a factor i through 1 to b, if a*i is divisible by b, then LCM(a,b) = a*i;
2) Improved LCM() algorithm:
- There exist a fantastic LCM algorithm with using the greatest common divisor(GCD) with Euclid's algorithm:
LCM(a,b) = (a*b)/GCD(a,b) , provided a*b >= 0
- And Euclid's algorithm in computing GCD:
GCD(a,b) = GCD(b, a%b) = GCD(a%b, b%(a%b)) = ....
3) Prime factorization LCM() algorithm:
By the unique factorization theorem, every positive integer can be factorized into product of primes with certain power.
e.g.
8 = 2^3
9 = 3^2
21 = 3^1 * 7^1
90 = 2^1 * 3^2 * 5^1
LCM(8,9,21,90)= 2^3 * 3^2 * 5^1 * 7^1 = 2520
It's easy to observe the pattern that the LCM is the product of multiplying the highest power of each prime number together.
So we can build a table(i.e. a hashmap or 2 arrays) of prime numbers and the highest power of each prime. Factorize each number from 2 to 20 and update the table of highest power of each prime. And multiple all the primes with powers to get the LCM.
[GitHub Link] [Official overview pdf by projecteuler.net]
Basically this is a problem of finding the least common multiple - LCM(1,2,3,...,20);
1) BRRRRRRUTE-FORCE ALL THE DAY:
Since LCM(a,b,c) = LCM( LCM(a,b), c), so we can compute the LCM binaurally.
To compute the LCM(a,b): loop a factor i through 1 to b, if a*i is divisible by b, then LCM(a,b) = a*i;
2) Improved LCM() algorithm:
- There exist a fantastic LCM algorithm with using the greatest common divisor(GCD) with Euclid's algorithm:
LCM(a,b) = (a*b)/GCD(a,b) , provided a*b >= 0
- And Euclid's algorithm in computing GCD:
GCD(a,b) = GCD(b, a%b) = GCD(a%b, b%(a%b)) = ....
3) Prime factorization LCM() algorithm:
By the unique factorization theorem, every positive integer can be factorized into product of primes with certain power.
e.g.
8 = 2^3
9 = 3^2
21 = 3^1 * 7^1
90 = 2^1 * 3^2 * 5^1
LCM(8,9,21,90)= 2^3 * 3^2 * 5^1 * 7^1 = 2520
It's easy to observe the pattern that the LCM is the product of multiplying the highest power of each prime number together.
So we can build a table(i.e. a hashmap or 2 arrays) of prime numbers and the highest power of each prime. Factorize each number from 2 to 20 and update the table of highest power of each prime. And multiple all the primes with powers to get the LCM.
[GitHub Link] [Official overview pdf by projecteuler.net]