Project Euler problem 3

Source code available on GitHub.

Here we go:

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

This is the first problem we’re going to need to split up into functions. We need a function to tell us the prime factors of any number, and to do that we need a function to tell us whether a particular number is prime or not.

Let’s start with the latter. While there are many fancy prime checks out there, we’re going to use the very simplest, most obvious one: just try dividing the number by every integer below its square root: if none of them go into it, then the number must be prime. (We only need to check up to the square root because factors come in pairs: if the number has a factor larger than its square root, there will be a corresponding one below it.)

So, if `number` is the number we want to check, we want a `for` loop to do what we just described:

for i in range(1,math.ceil(math.sqrt(number))+1):

In case the square root isn’t an integer, we round it up with `math.ceil()` and in case the square root is an integer, we add 1 so that the for loop will actually reach it.

Now, within this loop, we want to check whether `i` divides `number`, because if it ever does then `number` cannot be prime. Now is a good time to put it all into a function which will return `True` if the number is prime and `False` if it isn’t:

def isPrime(number):
    for i in range(1,math.ceil(math.sqrt(number))+1):
        if number % i == 0:
            return False
    return True

After testing this I realised that the numbers 1 and 2 confuse things, because 1 is its own square root and 2 is its own square root rounded up. So, we just add an `if`-`else` statement to protect against all that, and we’re done:

def isPrime(number):
    if number == 1:
        return False
    elif number == 2:
        return True
    else:
        for i in range(2,math.ceil(math.sqrt(number))+1):
            if number % i == 0:
                return False
    return True

Next, we want to find the prime factors of a number `number`. We can do this iteratively: as soon as we find one prime factor, we divide it out of `number` and do the whole process again with this new value. Eventually we’ll get to the last prime factor and `number` itself will be prime; this signals we’ve got them all.

We’ll follow a very similar approach to the function `isPrime(number)`. Starting with an empty list of prime factors, `primefactors = []`, we want to put everything inside a `while` loop so that when we change `number` we can do the whole thing again. Then, we want to check each possible factor of `number` just like we did above.

def primeFactors(number):
    primeFactors = []
    while True:
        for i in range(1,math.ceil(math.sqrt(number))+1):

This value `i` is a prime factor of `number` if and only if it divides evenly into `number` and it is prime. If both these conditions are met, we want to append it to our list of prime factors and then divide it out of `number` as mentioned above. Finally, we `break` out of the for loop and the enclosing `while` loop will make the whole process repeat with the new, smaller value of `number`:

def primeFactors(number):
    primefactors = []
    while True:
        for i in range(1,math.ceil(math.sqrt(number))+1): # Only check up to the square root: any other factors can be found from the existing ones
            if number % i == 0 and isPrime(i):
                primefactors.append(i)
                number = int(number/i)
                break

Note that we use `int(number/i)` instead of just `number/i` to get rid of any floating points that might accidentally be introduced in the division.

At the moment this will carry on forever: we need a termination condition. Once `number` is itself prime, it must be the last prime factor, so we can append it to the list and `break` out of the whole `while` loop. Then, we want our function to return our final list `primefactors`:

def primeFactors(number):
    primefactors = []
    while True:
        if isPrime(number):
            primefactors.append(number)
            break
        for i in range(1,math.ceil(math.sqrt(number))+1): # Only check up to the square root: any other factors can be found from the existing ones
            if number % i == 0 and isPrime(i):
                primefactors.append(i)
                number = int(number/i)
                break
    return primefactors

We’re done! All that’s left is to print off the maximum of this list for the specific value given in the problem, which we can do by taking `max(primeFactors(value))`. We also have to do `import math` at the beginning to allow use of the square root and ceiling functions.

Here’s the final code:

import math

def isPrime(number):
    if number == 1:
        return False
    elif number == 2:
        return True
    else:
        for i in range(2,math.ceil(math.sqrt(number))+1):
            if number % i == 0:
                return False
    return True

def primeFactors(number):
    primefactors = []
    while True:
        if isPrime(number):
            primefactors.append(number)
            break
        for i in range(1,math.ceil(math.sqrt(number))+1): # Only check up to the square root: any other factors can be found from the existing ones
            if number % i == 0 and isPrime(i):
                primefactors.append(i)
                number = int(number/i)
                break
    return primefactors

print(max(primeFactors(600851475143)))

Leave a Reply

Your email address will not be published. Required fields are marked *