Solving the Project Euler Problems – Problem 3

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

This problem is the first one that has taken some real effort, as no language seems to have any built-in function for determining whether or not a number is prime.

Part of my memory however is convinced that the R language, which I first worked with all the way back in university, did have a function to list all the prime factors of a number, so either my memory is corrupted or, well, chances are it is, as even after sending hopeful texts to people I’m still in touch with from that same course I came up dry. Relearning R is something for another day though, so for this problem, Python it is!

The reason for Python over PHP, as I could just as unhappily do this one in PHP, is that the point of doing these exercises is to expand my knowledge of multiple languages rather than just “solve them”.

Going forward I will likely solve these in a number of languages, but I certainly envisage the main 2 being PHP and Python.

Trying to work out a function that would return the prime factors of a number has turned out to be a huge pain, and even then by looking at the code you’ll see I still haven’t managed it! This function does however iterate through the number, reducing it down to its highest prime factor, also covering the case where our number itself is prime.

I even tried venturing into the world of generators and using yield rather than return – definitely something to leave for another day frankly, maybe later in these problems, who knows?

Leave a Reply

Your email address will not be published. Required fields are marked *