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)

Project Euler Problem 2 (Python)

Alright, for this problem let's switch things up a bit and go with some Python code. I'm currently working with Python on some projects for college, so I decided to go ahead and solve some of these problems in Python rather than continue on in Java.
Also, I'm going to try and make the posts much shorter and to the point. I'm assuming anyone that reads these has at least a basic programming knowledge. (loops, if-statements, variables, functions, classes, etc.) Anything complex will still be explained, but I'd like to simply describe the problem and the steps to solving it. Typing up long explanations of basic programming constructs is time consuming and also probably not helpful. There are plenty of beginner programming tutorials out there, and if problems arise, then questions can be asked in the comments section.
Ok, enough talk, let's see what the second problem has in store for us.

Problem 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

--

To solve this problem we know we need a few things:

* We have to be able to calculate the numbers in the Fibonacci sequence.
* We need to be able to loop through the numbers in the sequence and add each number to a running total.
* We need a way to determine if a number in the sequence is even, and if so add it to the sum.
* We need to check when the number in the sequence is greater than 4,000,000 and then stop looping.

Fortunately, all 4 of these things can be done with basic programming constructs. The numbers in the Fibonacci sequence can be generated very easily by following the description given in the problem. A simple while loop can be used to loop through the numbers, and each time we can add to a variable that holds the sum. Determining if a number is odd or even can be done by taking the modulus of the number and seeing if it is 0. If it is, then we know that the number is even and add it to the sum. We make our condition for the while loop break out of the loop if the number exceeds 4,000,000.
That's all we need to solve this problem. Assemble these components correctly and we should get a program that gives us the correct answer.

Here's what I ended up with:


Thanks for reading!
-Michael

Update: After reading through some discussion of this problem, I've realized that there is definitely a better way to solve this problem that would remove the need for the use of the modulus operator to check if a number is even. By writing out some of the Fibonacci sequence, it becomes apparent that every third number is even. This makes sense, and is fairly easy to prove mathematically. Anyway, that being said, we could simply have looped through and added up every third number rather than using an if-statement to check for an even number. I'm not going to post new code, but I thought I would mention this optimization.