Project Euler/5

Problem 5 on Project Euler: https://projecteuler.net/problem=5

Solution: https://git.charlesreid1.com/cs/euler/src/master/005

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://git.charlesreid1.com/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, we 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).

Illustrative Example

Let's do this to find a least common multiple of a group of numbers.

Start with the first three integers: 1, 2, and 3. (For our purposes, 1 doesn't contribute anything so we will not count it.

Break down each number into its prime factorization: 2 => 2, 3 => 3. No prime factors are shared, so we multiply all the factors together and get an LCM of 6.

For the first four integers, 1, 2, 3, 4, now 4 can be written as 2 * 2, so we write the minimum prime representation as 2 * 2 * 3, LCM is 12.

On to first 5 integers: 1 2 3 4 5 break up into prime representation of 2, 3, 2 * 2, 5. The minimum set there is 2 * 2 * 3 * 5 or 60.

We can also form 6 out of the same set, so we know that 60 is also the LCM of the first six integers.

To get the LCM of the first seven integers, 7 adds a new prime factor, so we get a new LCM of 420.

Getting the prime factorization of 8 requires one additional 2, so we get an LCM of 840, which is the product of 8 and 105.