Project Euler Problem 3 (Python)

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 a little more difficult than the previous problem, but it still isn't overly complex. The first thing to notice is that this problem can be broken down into two pieces. First, we know that somehow we need to be able to generate prime numbers, or at the very least we must know how to determine if a number is prime or not. Secondly, we need to be able to factor a number and store it's factors.

I chose to create a class to hold the list of prime numbers. There are various ways you can go about listing/generating prime numbers, but I use with a simple sieve method. Basically, you start with a list of a few prime numbers, and then to generate a new one you start counting up from the last prime until you find a number that isn't divisible by any of the primes currently in the list. I'm sure there are faster methods to go about doing this, but I went with a fairly intuitive and easy to implement method. This makes up my "__genNextPrime" function. As a side note, the double underscores in the method name denote it as a private function in Python. The "nextPrime" function returns the next prime number, and handles the calling of the "__genNextPrime" function when needed. There is also a function that resets the index to 0 so that the next prime number returned is reset to the first one.

That takes care of the task of generating prime numbers, so what about factoring this large number? First we store the number provided from the website in a variable. It's important to note here that we are spoiled by using Python. In many languages, a number such as 600851475143 is much too large to store in the typical integer. In order to deal with it you would have to explicitly declare it as a "long". However, Python automatically handles the data types, so it knows which type of number to use in each situation. Anyway, back to the solution. We also have to declare a list to hold each of the prime factors. Now the interesting stuff begins. In English, we want to continue looping until the original number is completely factored. In the loop, we want to get a prime number, and see if it is a factor. If it is, then we add it to our list, set the number equal to the number divided by the factor, and then reset the index of the primes. If it's not a factor, we just get the next prime and repeat the loop for that new prime. How do we determine if the number has been completely factored? Well, if the primer number we are testing as a factor is greater than the square root of the number, then it can't be a factor. Why? Because we already know that all the smaller primes are not factors if we've gotten that far in the loop. Once we break out of the loop, then if there is any remainder, then that gets added to the list of prime factors. Finally, we simply print out our list of prime numbers.

If all this confused you, then maybe a look at the following source code will help. It's easier to put into code than words. (Click on the image to make it bigger so the program is readable)