Solving mathematical problems using code: Project Euler

James Rhee
Aug 24, 2017 · 4 min read

It is week 9 here at the Flatiron school and we are now approaching the end of our first module with Javascript. We have been so busy trying to digest all the new material that we have had barely anytime to catch a break. Everyday seems so long and packed yet there is never enough time. We have been moving at an accelerated pace, uncovering new topics when we are starting to barely grasp the material we are currently on. So to take a short breather from all this, I decided to take a step back to the very beginning stages of my coding journey and introduce you all to my friend Project Euler.

Project Euler

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

I discovered Project Euler through a friend who recommended I try solving the problems on the site to enhance my coding skills to prep myself before attending a coding bootcamp. Project Euler is a site with many mathematical problems that are intended to be solved in an efficient way using code. The problems are labeled with the description/title, number of users that solved the problem, the difficulty level, and status of the problem (whether I solved it or not). Some of the problems also provide a PDF file that shows a mathematical approach to the problem using algorithms once the question has been solved.

Let’s take a look at one of the problems on the site:

“The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?”

We are first given an example explaining what a prime factor is. From what we can tell, a prime factor is a number that is evenly divisible by a number and is also a prime number. Then we are given the number 600851475143 and are told to find the largest prime factor of this number.

Now let’s take this step by step and try to solve this problem using our coding knowledge.

First we need a method or function that can check whether a number is a factor of 600851475143. We also need a method or function that can check whether that number is a prime number.

Then we build out our largest_prime_factor_of(n) method to find the result.

In our new method, we are checking to see if every number between 1 and 600851475143 is a prime factor. If it is, then we select and store that number in an array and call .last on the array to return the greatest prime factor. Now I’m sure our logic works perfectly fine but when I ran this code, it went on for longer than 5 minutes so I terminated the process. Since 600851475143 is a very large number, it takes quite a bit of time for the system to calculate whether each number up to the given number is a prime factor or not.

So instead of having to calculate every single number up to 600851475143, we can simply reject all the numbers we don’t want to calculate using prime factorization. We can do this by dividing the number by it’s first prime factor until the only prime factor is itself.

Great! We can now see that our code returns the correct value in an acceptable amount of time. But we can further refactor this code to be more efficient than it is now by requiring and using the built in ruby Prime class.

Noice.

Sources

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade