Project Euler/5

Project Euler Problem 5

Least common multiple problem.

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?

Project Euler Link: https://projecteuler.net/problem=5

Solution code on git.charlesreid1.com link: https://charlesreid1.com:3000/cs/euler/src/master/Problem005.java

Notes

The naive approach is to simply say, multiply all 20 integers together. That gives you 20!, a very large number.

The next approach is to find the smallest number that is evenly divisible by all the integers i = 2 through n, and if it is, print it out.

Unfortunately, while this integer is much smaller than 20!, it is still too big to find in a brute force for loop.

There must be a better way!

Indeed, this problem boils down to finding the least common multiple, and a simple examination of 5! = 120 reveals the right approach:

1*2*3*4*5 = 120 only has one repeated prime factor, a 2.

The least common multiple also happens to be small enough to find in our head, namely, 60, or 120/2.

So, we find any duplicate primes, like 2 and 2^2, and replace them with just 2^2.

If we find the prime representation of each integer, then we find the minimum prime representation shared by all of these integers, we will find our least common multiple.

This will require getting a list of prime numbers up to 20 (whew!), and the prime factors representation of a given integer (easy to do if we can get all the primes up to that number).