## Problem:

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

What is the largest prime factor of the number 600851475143?

*Source: http://projecteuler.net/index.php?section=problems&id=3*

## Solution:

Before we can being to solved the problem above we first must answer the questions raised by it. In other words:

- What is a prime number?
- What is a factor?
- What is a prime factor?
- How do we find the prime factors for a number?

### What is a prime number?

A prime number is any natural number that can only be divided by 1 or itself. E.G. 7 is a prime number because it can only be divided by 1 or 7 while 10 is not a prime number because it’s divisors are 1,2,5,10.

### What is a factor?

A factor (also known as a divisor) is any number that that can divide in to another number and not leave a remainder. In the previous section about prime numbers you can see the for 10 it’s factors are:

- 1
- 2
- 5
- 10

### What is a prime factor?

A prime factor is any factor that is also a prime number.

### How do we find the prime factors for a number?

The method of finding prime factors is called Prime Factorisation. It involves taking a number and dividing it by the smallest prime possible, then taking what’s remaining and dividing that by the smallest prime possible; keep doing this until the remainder is a prime. This Khans Academy video offers a great introduction to this concept.

## Code:

*Source: https://bitbucket.org/TWith2Sugars/project-euler/src/8892d0a39946/python/3.py*

def primeNumbers(n): # Found this example on Wikipedia: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes # Create a candidate list within which non-primes will be # marked as None; only candidates below sqrt(n) need be checked. candidates = list(range(n+1)) # Square root of n fin = int(n**0.5) # Loop over the candidates, marking out each multiple. for i in xrange(2, fin+1): if candidates[i]: candidates[2*i::i] = [None] * (n//i - 1) # Filter out non-primes and return the list. return [i for i in candidates[2:] if i] def primeFactors(n): # Generators all of the prime factors for n # The largest number that a prime factor could be maxPossiblePrimeNumber = int(n**0.5) # List of all prime numbers up to the square root of n primes = primeNumbers(maxPossiblePrimeNumber) while n > 1: for p in primes: # This is a prime factor if n % p == 0: # Set n to be the result of the division of n by the current prime number (p) n = n / p yield p maxPrime = max(primeFactors(600851475143)) print(maxPrime)

The code is broken down in to two parts:

- Generating Prime Numbers (
*primeNumbers*) - Performing Prime Factorisation (
*primeFactors*)

### Generating Prime Numbers

There are many methods of generating prime numbers and in my search I’ve decided to use a method called Sieve of Eratosthenes which is pretty efficient are generating prime numbers below 100. It also comes with a python example that we can use. You’ll see the code below.

### Performing Prime Factorisation

This function just implemented the method of finding prime factors as mentioned earlier, there is probably a more efficient/mathematical way of doing this but for now it’s a good start.

## One comment

same probem solved in c#

https://sites.google.com/site/eulerproblemsincsharp/home/problem-3