Project Euler: Problem 3

Largest Prime Factor

Photo by Fotis Fotopoulos on Unsplash

Problem:

What is the largest prime factor of the number 600,851,475,143?

Approach:

This one was very useful if you have some math background.

Any non-prime number can be represented as the multiple of its prime factors, meaning for example, 21 = 3 x 7 or 1,234,567,890 = 2 x 3 x 5 x 3607 x 3803.

A simple way to determine the prime factors of a number is the following algorithm:

Set k = 2.
Check if the number is divisible by k. If so, the new number becomes old number divided by k.
Increase k by 1.
Repeat until you’ve found all the prime factors (ie new number = 1).

This is effectively what I did here.

Challenges:

I noticed a few things with this one.

It is difficult to know when you’re “done” checking for prime factors.

I initially wrote a function that would check through every number from 2 to the number specified, but found that with the goal of a little over 6 trillion, it took a really long time.

So my quick-and-dirty solution was to set a limit on numbers to check. In other words, just check factors between 2 and some limit, which I set to 1 million. I figured the answer would be factors below that limit.

However this approach quickly breaks down.

What if:

Goal Number = 2 x (a prime number over the limit)

Then this approach fails.

However, my crappy first go was good enough to get the correct answer to the quote.

Solution:

Here.

Next Steps:

My mistake with the first approach was to use a for loop with a pre-set end point, rather than a while loop using the condition of finding the largest prime factor.

I wrote a second function which uses a while loop until the condition that the number that is being divided in sequence, in this case “c”, is equal to 1. This indicates that the number cannot be divided any further and you have found all prime factors of the number.

This function is not only faster (it stops when the factors have been found) but doesn’t stop prematurely.

The speed of this function is thereby determined by the largest prime factor, which is acceptable for me.