What is the largest prime factor of the number 600851475143 ?

[Full Question]

Answer

from math import sqrt
from math import ceil

#this function will determine if 
# num is prime
def isPrime(num):
	i = 2
	isPr = True
	numSqrt = sqrt(num)
	while i < numSqrt and isPr:
		if num % i == 0:
			isPr = False

		i += 1
	return isPr

largeNum = 600851475143 
curNumber = 3
largestPrimeFactor = 0
#only need to go as far as the 
# square route of the number 
# because we check the other factor
# when we find the first
maxCheck = ceil(sqrt(largeNum))

while curNumber <= maxCheck:
	if largeNum % curNumber == 0:
		#found a factor check if it is prime
		if isPrime(curNumber):
			#check if larger than largest prime
			if curNumber > largestPrimeFactor:
				largestPrimeFactor = curNumber
			
			#number isn't prime, check
			#if the other factor is prime	
		elif isPrime(largeNum / curNumber):
			#matching factor is prime check if larger than 
			#largestPrimeFactor
			if largeNum / curNumber > largestPrimeFactor:
				largestPrimeFactor = largeNum / curNumber
				curNumber = largeNum / curNumber
	
	#increment by 2, so we don't check even numbers		
	curNumber += 2

print "The largest prime factor is %d" % (largestPrimeFactor,)

[Download Code]

Getting a little more complicated here. Starting with defining a funciton to determine if the current number is prime. At first pass, this took very long if you try to check all the numbers. Then I realized you only had to check until the square root, and then from all the factors before the square root, you could find the factors above the square root.