I love programming competitions.  In the past two years I’ve participated in both my school’s programming competition and the ACM Southern California regional competition.  Recently I’ve been turned onto http://projecteuler.net which is a competition-like site that gives you a series of math questions which you need to solve by writing a program.  I saw this as a good opportunity to brush up on python, so today I’ve been trying my hand at a few of these problems.

Question #3 asks you to find the largest prime factor of a very large number.  My first instinct was to start at Sqrt(n) and work my way back until I find the first factor.  The problem here is that the first factor you find may not be the first PRIME factor.  Instead, my approach to this problem was to find all factors of the number between 2 and Sqrt(n) and put them in in a list.

Of all the numbers in the list, one of them is the largest prime factor, but which one?  To find out, I made an assumption that turned out to be right:  The composite factors have at least one prime factor that is already in the list.  If I can show that a given number has no factors in the list, then it is a prime factor.  Further, if I have a sorted list and start at the end, I can show that the number is the largest prime factor.

Anyway, here’s the code I used:

n = 600851475143 # Find the largest prime factor of this
div = [x for x in range(2,int(math.sqrt(n))) if n % x == 0] # Get all factors
i, j = 0, len(div) - 1
while j > i: # Determine which one of the factors is the largest prime

# This number is composite, go to the next largest factor
if div[j] % div[i] == 0: i,j = 0,j-1
# See if the next number at the beginning of the list divides the current number
else: i += 1

print div[j] # Print out the largest prime factor