My solutions to the problems found at Project Euler.
Jump to: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 16 | 17 | 20 | 21 | 22 | 25 | 3-2 |# /usr/bin/python
# Problem: Find the largest prime factor of 600,851,475,143
#
# After some thinking and jotting down on a piece of paper, I came up with a
# much improved attack plan that doesn't rely entirely on brute force.
#
# Attack plan number 2!:
#
# a) Find the lowest number our number is divisible by, and divide it (LCD).
# b) Continue this process until our number is prime.
# c) Voila, that (should) be our highest prime factor.
def find_lcd(n):
simple_lcds = [2,3,5]
for simple_lcd in simple_lcds:
if n % simple_lcd == 0:
return simple_lcd
possible_lcd = 7
while possible_lcd < n:
if n % possible_lcd == 0:
return possible_lcd
possible_lcd += 3
return None
def find_highest_prime_factor(n):
if find_lcd(n) == None:
return n
else:
return find_highest_prime_factor(n / find_lcd(n))
if __name__ == '__main__':
n = 600851475143
print 'The highest prime factor for ' + str(n) + ' is ' + str(find_highest_prime_factor(n))