# returns True if parameter n is a prime number, False if composite and "Neither prime, nor composite" if neither def isPrime(n): if n < 2: return "Neither prime, nor composite" for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True # returns smallest factor of parameter n def findSmallestFactor(n, i): if n % i == 0: # found it return i elif i > n: # can't find it; something's wrong return -1 else: # keep trying return findSmallestFactor(n, i + 1) def greatestPrimeFactor(n): # finding smallest factor increases performance IMMENSELY with numbers very large. # for smaller numbers, just use: # for i in range (int(n / 2), 1, -1): smallestFactor = findSmallestFactor(n, 2) for i in range (int(n / smallestFactor), 1, -1): # start with the largest factor and go down to 2 if n % i == 0: # check if it's even a factor before checking if it's prime if isPrime(i): # THEN check if it's prime (better performance to do it now instead of before) return i return n # if it didn't already return something, there's nothing left to look for, so the number itself is prime # This function skips a lot of numbers by dividing by potential factors into the original number; # it starts at the smallest factor, and continues until the largest factor (number / smallest factor) def greatestPrimeFactor2(n): smallestFactor = findSmallestFactor(n, 2) # this loops through the small factors first, but tests the large factors by dividing the number by the factors, i for i in range (smallestFactor, int(n / smallestFactor) + 1): # for the smallest factor to the largest factor (inclusive for both) if float(n)/i == int(n/i) and n % n/i == 0: # if it's an integer and the number is divisible by the corresponding factor if isPrime(n/i): # THEN check if it's prime (better performance to do it now instead of before) return n/i return n # if it didn't already return something, there's nothing left to look for, so the number itself is prime # examples print (greatestPrimeFactor(60)) # 5 print (greatestPrimeFactor2(13195)) # 29DOWNLOAD

Created: February 12, 2014

Completed in full by: Michael Yaworski