Project Euler Problem Number 3

Project Euler problem 3 reads as follows:

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

There are no special Python features here that really require explaining. The logic is also straightforward: find the smallest prime that divides evenly into "number"; reset "number" to number/prime; if prime is greater than the square root of number, you have your answer. Solution works in both Python and IronPython.

def GetNextPrime(allPrimes):
    """Given a sequential list of prime numbers, return 
    the next prime number
    """
    value = allPrimes[-1]
    if value == 2:
        return 3
    
    while True:
        value += 2
        for prime in allPrimes:
            if value % prime == 0:
                break;
        else:
            return value

def Euler003(number = 600851475143):
    # import the square root function, seed the primes list
    # and determine what
    # the largest possible factor
    from math import sqrt
    primes = [2,3]
    limit = sqrt(number)
    
    # if the last prime number exceeds our limit, we're out
    while primes[-1] <= limit:
        for prime in primes:
            if number == prime:
                # if the prime and the number are the same, 
                # we've found our answer. break out of
                # the loop
                return number
            elif number % prime == 0:
                # number isn't prime! largest prime factor
                # will be in number/prime.
                number /= prime
                limit = sqrt(number)
                break
        else:
            # still didn't find number % prime == 0? Maybe
            # we need bigger prime numbers
            while primes[-1] <= limit:
                # get next prime number
                primes.append(GetNextPrime(primes))
                # if number is divisible by next prime number
                if number % primes[-1] == 0:
                    if number == primes[-1]:
                        break
                    number /= primes[-1]
                    limit = sqrt(number)
                    break
    return number

print Euler003()

Project Euler Problem 2

Problem number 2 reads "Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million." The resolution to this problem is not quite as simple as the previous one, but it's not far off.

def fib(maxFibNumber):
    a, b = 0, 1
    while a < maxFibNumber:
        if (a % 2 == 0):
            yield a
        a, b = b, a + b

print sum([x for x in fib(4000000)])

This time we can't rely entirely on list comprehension for the answer. We have to define the fib(maxfibnumber) function that will calculate our Fibonacci sequence and return only even those that are even. I modified a Fibonacci function I found at literateprograms.org to do the job. I have to mention one of the little niceties that makes Python so useable: multiple assignment. Multiple assignment describes the technique of assigning - *binding* in Python - two variables simultaneously. We bind "a" and "b" as soon as we enter the "fib" function and then rebind them at the end of the while loop. This is just another way Python can help us with a simple programming idiom.

Taking on Project Euler with Python

Lately a number of posts on Project Euler, a series of predefined mathematical/computer science puzzles, have come to my attention. Bill Wagner has started a series of posts solving the Euler problems in C# and Dustin Campbell has posted one solution in F#. Several of my co-workers at SRT Solutions have been working through solutions in Ruby, Scala and Boo. My contribution will be in Python.

Project Euler problem 1 reads as follow: "Add all the natural numbers below 1000 that are multiples of 3 or 5." Python's list comprehension makes the solution to this problem trivial.

print sum([x for x in range(1,1000) if x%5==0 or x%3==0])

List comprehension is really just shorthand for a loop that sticks a variable into a sequence. In this solution, the loop is represented by the "for x in range(1,1000)" portion of the statement and a condition is added immediately following. The first "x" really just represents any value that is added to the sequence assuming it gets by our condition. Use the built-in "sum(list)" function and we have our answer. Simple, elegant and very readable.