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
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s