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?
The main consideration here was how to calculate the Fibonacci sequence without taking up too many resources, a common danger with recursive functions which are often touted as the solution for working out the sequence and other things like factorials. It turns out the Fibonacci sequence as a recursive function is fine up until about the 10th term, but any further than that? Not advisable!
The much quicker solution that I’ve found is to do it as an array, which takes simple values for its calculations rather than calling a recursive function again and again and again.
The second performance optimisation is checking whether our Fibonacci number is even, which when doing it a limited number of times, is fine to do just by checking if n modulo 2 is 0, but how many times will we be doing this? Off the top of your head which Fibonacci term is the largest below 4,000,000? The 10th? The 50th? The 1,000th? We don’t know how many until we actually do it. As it happens it’s the 32nd term, 3,524,578. Run that recursive function 32 times!
As division is slow and all we’re using it to do is check if a number is even, is there a better way? Well kind of, we can check if it isn’t odd. This is done by using the bitwise AND operator. This takes the binary representation of a number – 2019’s would be 11111100011 – and it’s that final bit we’re interested in, if it’s 1 then the number is odd and if it’s 0 it’s even. So using the bitwise AND operator to compare any number to 1 checks only 2 bits and avoids division.
After stumbling across an article on Medium by Bennett Garner, I discovered the Project Euler problems and that it would be a good idea to showcase my skills in solving them in a variety of ways, as a good starting point to get a code portfolio going, so here goes with – as natural a starting point as any – problem 1!
All of the Project Euler Problems can be found at ProjectEuler.net.
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
There were 2 ways I considered to tackle this:
- Loop from 1 to 1000 (or as in the code, n) and check each number for dividing by 3 and 5 respectively, adding them to the result if either is true
- Reduce the number of loops by 47% and run our loop + n/5 times (for those interested, 1/3 + 1/5 = 8/15, so this reduction percentage works for any integer), by dividing n by 3, running that loop, adding 3 times each number to the result – which takes division out of the loop as well – then doing the same again, only now having to check (on a smaller loop) if our result was already added as being a multiple of 3.