#The prime factors of 13195 are 5, 7, 13 and 29.

#What is the largest prime factor of the number 600851475143 ?

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,)