# /usr/bin/python
# Problem: Find the largest prime factor of 600,851,475,143
#
# My attack-plan: I'm not very mathematically inclined. I don't know any clever tricks for this
# problem. My attack is very straight-forward.
# 
#   a) Write a process for finding all whole factors of a number.
#   b) Write a process for determining whether or not a number is prime.
#     1) This should be easy with (a) completed. A prime number will have a factor
#        list of two. Itself and 1.
#   c) Chain those two processes and hopefully get the right answer!
#
# Attack plan number one has failed me. It works, but is far too slow.
# I've given the code some thought, and have a new attack plan.
# See 3-2.py :)

import sys

def find_whole_factors(n):
  " Create a list of all whole-number factors for any given n"
  factors = []
  possible_factor = n
  print 'Generating all factors for ' + str(n)
  while possible_factor > 0:
    print 'Testing possible factor: ' + str(possible_factor)
    if n % possible_factor == 0:
      print '  Factor found: ' + str(possible_factor)
      factors.append(possible_factor)
    possible_factor -= 1
      
  return factors
  
def is_prime(n):
  " Determines whether or not a number is prime. "
  print 'in is_prime of ' + str(n)
  print find_whole_factors(n)
  if len(find_whole_factors(n)) == 2:
    return True
  
  return False
  
if __name__ == "__main__":
    n = 600851475143
    factors = find_whole_factors(n)
    
    print 'Attempting to search for the highest prime factor of ' + str(n)
    for factor in factors:
      if is_prime(factor):
        print 'Highest prime factor found: ' + str(factor)
        sys.exit()
        
    print 'No Prime factors found.'
    sys.exit()