Project Euler Problem 3


For project Euler problem 3 we work on a few basic principles that we will use for several upcoming problems (yay reusable code!), factorization and determining whether a number is prime. Here is the problem:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

One way one could complete this problem would be to find all factors of the given number, and loop through checking if they are prime, returning only the largest one. To start out, let’s find all factors of a number.

import math
def findAllFactors(number):
    factors = list()
    for i in xrange(1, long(math.sqrt(number))):
        if number%i == 0:
            factors.append(i)  
    return factors

Here, we are simply looping through the numbers between 1 and the square root of the number, looking for numbers that divide evenly into our original number. Numbers that divide evenly are factors, so we add them to a list which we return afterward. Alternately, we could create a generator to return all factors:

import math
def findAllFactors(number):
    for i in xrange(1, long(math.sqrt(number))):
        if number%i == 0:
            yield i 

Next, we loop through each factor, checking to see if it is prime using the following code:

def isPrime(n):
    n = abs(long(n))
    if n < 2:
        return False
    if n == 2: 
        return True
    if not n & 1: 
        return False
    for x in range(3, long(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

If we have a prime factor, let’s toss it in a list for now:

if __name__ == "__main__":
    factors = findAllFactors(600851475143L)
    primeFactors = list()
    for f in factors:
        if isPrime(f):
            primeFactors.append(f)

or if you are using the generator:

if __name__ == "__main__":
    primeFactors = list()
    for f in findAllFactors(600851475143L):
        if isPrime(f):
            primeFactors.append(f)

Now we simply grab the largest number in the list by sorting it and grabbbing the last item!

    primeFactors.sort()
    print "The Correct answer is: %d" % (primeFactors[-1])
Advertisements

Python “yield” and Project Euler problem 2


When working on Project Euler problem 2, I stumbled on a unique feature of Python: the yield keyword. The yield keyword allows for the creation of generators. Generators are defined much like functions, but have the added bonus of being able to return multiple values over the course of their execution. For example, lets say I wanted to make a function that counted from 0 to infinity, and kept it’s state between uses. The following generator would do just that:

def counter():
     a = 0
     while True:
          yield a
          a += 1

Simple isn’t it? Iterating through it is simple too. Let’s say we want to get the first 10 numbers, and then the next 20, with a break in between:

if __name__ == "__main__":
     x = counter()
     for i in x:
          if i < 10:
               print i
          else:
               break
     print "Broken out of counter"
     for i in x:
          if i < 30:
               print i
          else:
               break

The output would be:

0
1
2
3
4
5
6
7
8
9
Broken out of counter
11
12
13
.
.
.
23
24
25
26
27
28
29

Now to make this relevant. Project Euler problem 2 is as follows:

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.

So what we need to do is find a way to take the starting values of 0 and 1, and as each iteration passes, set a to the value of b, and b to the value of a+b, returning a each time. Sounds like a job for generators!

def fibonacci(max):
     a, b = 0, 1
     while a < max:
          yield a
          a, b = b, a+b

Next, we loop through each of the returned values, checking if it is even. If so, add it to a running total.

def sumEvenFibonacciNumbers(max):
     number = 0
     for n in fibonacci(max):
          if n%2 == 0:
               number += n
     return number

if __name__ == "__main__":
     print sumEvenFibonacciNumbers(4000000)

There you have it, using generators Project Euler problem 2 was a breeze!

Getting Started with Project Euler


If you haven’t already, go ahead and sign up at Project Euler. Once you have logged in, head on over to the Problems page. I recommend sorting the problems by ascending difficulty, as this will allow you to tackle the problems in a (more or less) gentle slope, at least at first. Let’s take a look at the first problem:

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.

So where do we get started? The key to this problem is the modulo operator. For those who are unfamiliar with the modulo operator (notated in many languages as % ), it divides two numbers and returns the remainder. So, if a number divides evenly by 3 or 5, we want to add it to a running total. So, if we were to look at this problem in language-agnostic pseudo-code we would get:

for each number between 0 and 1000
     if number/3 evenly, or number/5 evenly
          add the number to a running total
print the total to the user

With that, you should be able to complete this problem fairly quickly. If you would like to see this problem implemented in a few programming languages, hit the Read link below:
(more…)

Project Euler and Learning Python


A few months ago I decided it was time to start learning Python. I had heard great things about python,

The Joy of Python

It's the Python

and I couldn’t in good conscience let an opportunity pass to learn a new language. I grabbed a copy of “Dive Into Python” from the internet (see the link on my sidebar) and got started. I spent a few days writing simple apps going along with the book, but got bored fairly quickly. As someone who has conquered several programming languages at this point, it is difficult to find your mind stimulated by programs designed for new programmers. After a few Google searches, I stumbled upon Project Euler. For those who are not familiar with Project Euler, it is a collection of language-agnostic programming/math problems that are designed to help programmers keep (or develop) their edge. Each problem is designed in such a way that an efficient algorithm should provide the correct answer in 60 seconds or less in any language. I decided to give it a go, and have enjoyed myself greatly in the process. I plan on attempting to complete each challenge in a variety of languages, in an attempt to compare and contrast each language. How many of you have tried Project Euler, and what has your experience been?