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

i have a question..

what is contained in your list?? alla the factors or all the prime factors between 2 and sqrt(n)..?? what makes sure that there will not be any prime factor above sqrt(n)??

can you explain it further… and your hypothesis,too..

thanks

awesome

This only work with very large numbers where the largest prime factor is lower than the square root of that number!

This method will fail when trying to get the largest prime number of 20 for example. your method returns 2 instead of 5.

In response to the comments:

Since I wrote this I have delved deeper into number theory. My hypothesis is based on the fundamental theorem of arithmetic which states that any number is prime or the product of prime numbers. Since we have found all prime numbers that make up the factorization of the given number, we can conclude that any composite numbers are also made up of the given prime numbers.

@Simon: You’re absolutely right! I found that numbers that are made up of primes that are close together will fail. For example, take the square root of 3559 * 3571; you get 3564. Clearly my algorithm would fail for this case. This might make for an interesting study though.

the loop need to run till (n/2) and not sqrt(n). The largest factor of n is n. The next largest can only be (n/2).

@Raison: The largest factor of n is n. Yes this is true, but we’re talking about prime factors here. A proof of what I assumed to be true can be found here: http://math.stackexchange.com/questions/102755/greatest-prime-factor-of-n-is-less-than-square-root-of-n-proof/102760#102760