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
#
# 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()