The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?
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:
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.
def primeNumbers(n): # Found this example on Wikipedia: //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.