/code/blog

Code, code and code

The Largest Prime Factor of the Number 600851475143

Problem Statement We need to compute the largest prime factor of a particular number - in this case 600851475143 Notes We define a new prime factors generator which generates all the prime factors of a particular number (not including 1). After that it is trivially easy to use the max function around its results to find the maximum prime factor. To generate the prime factors we use a while loop on the number itself being greater than 1. The reason we do that is that once we find a prime factor, we divide the number by the prime factor, and continue further processing with the number being now set to the quotient of the division. One usually only needs to search within 1 and the square root of a number to find a factor (since one of any two factors of a number is always less than the square root of the number). Since we use it in the range operator (which is non inclusive of the upper end) we add 1.0 to it. However there are situations when the number itself is a prime number. We would like to return the number in such a case - but that is clearly not an option when the for loop continues only until the square root of the number. Hence we use the chain function from the itertools library to chain a sequence with the number itself at the end of the for loop (which itself is another generator). The chain operator effectively creates a continuous sequence spanning the first and the second generator. We only take the first element from this combined sequence and yield it (as a generated value). That value is the lowest prime factor for the number. Having yielded the prime factor, we divide the number by that factor and resume processing on the quotient. Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import chain

# A function which just takes the first value from a generator
# and ignores the rest
def first(gen):
    try:
        return gen.next()
    except StopIteration :
        return None

# A generator to return the prime factors of a number
def prime_factors(n):
    while n > 1 :
        ff = first(val for val in chain(
                        xrange(2,int(n**0.5+1.0)),[n]) if n % val == 0)
        yield ff
        n = n / ff

# Actual computation
print max(prime_factors(600851475143))

Comments