In this article, we’ll explore project Euler problem 5. I’ll provide some of my own ideas and hints, and then you can attempt to create a program that provides a solution on your own. Be sure to stay updated on my blog for the full walkthrough article that I’ll post soon!
Note: This is not a walkthrough article. In this article, I’ll discuss the problem and share some ideas, but I won’t actually walk you through on how to write the solution. Try implementing the ideas in this article into a program that solves the problem, but if you get stuck don’t worry as you can read the walkthrough article for this problem for the solution.
This article is part of the Project Euler series.
Project Euler Problem 5
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 problem is asking us to find a number where each number between 1 and 20 will fit into that number. In other words, what is the LCM (Least Common Multiple) of the numbers 1 through 20?
Now, we could just try dividing each number by every number between 1 and 20 to see if it is evenly divisible by all the numbers, but that is a lot of operations and slow and inefficient. Here are some ideas I have about this problem:
Narrowing down our factors
After some thinking, I realized that every number that is divisible by 20 is also divisible by 1, 2, 4, 5, and 10. Therefore, we don’t have to check to see if those numbers are a factor as long as we check that 20 is a factor.
You can repeat this process for every number and make the number of numbers we check as small as possible. Obviously you won’t be able to remove the prime factors like this, but you can still size down the factor set significantly.
Optimizing our solution
When it comes to problems like these, in my opinion, the problem is more about optimizing a solution rather than just getting an answer. I could write a program in a minute without thinking to solve this problem, but what good does that provide to me? If I take the time to study the problem and everything behind it then I can become a better programmer.
If something is divisible by the numbers 1 to 20, it is divisible by 1 to 10, as those numbers are in the range. Mathematically, this means if that something is divisible by the numbers 1 through 20, it is also a multiple of 2520. The problem even provides this number for us!
There are probably many other ways to optimize this solution that I haven’t been clever enough to think of, but hopefully, after reading this article you have a starting point on how to approach project Euler problem 5!
Here’s the walkthrough article for project euler problem 5. In this article, I discuss the actual solution to this problem by implementing the ideas I discussed above.
