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 |

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

jb