# Project Euler problem 3

Source code available on GitHub.

Here we go:

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)))```