On 12/02/2011 12:15 AM, Robert Sjoblom wrote:
So I've recently started poking at the Project Euler site, because I feel that I need to practice writing code. For those of you interested in solving the problems on your own I advice you to not read this, as it will spoil the solution.Problem 3 is this: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? I came up with this pseudocode: #pseudocode: # divide by x until non-prime is found: # if not remainder: # check if it's prime or not: # if not prime: exit loop # if not prime: store in variable # increment x by 1 Here are the functions I came up with: def isprime(n): if n == 1: return False for x in range(2, n): if n % x == 0: return False else: return True def factorization(n): factor = 0 x = 2 while True: if n % x == 0: if isprime(x): factor = x else: return factor x += 1 This, however, feels horribly inefficient. Is there a better way to do it? I think most of my problems stem from my weak mathematical skills, to be honest. This wasn't too bad, but even for problems 1 and 2 I've relied on brute forcing the answer instead of looking for a mathematical solution.
With regards to primes, check out Sieve of Erastothenes; if you need to generate a "list of primes" instead of doing just "primality check", the sieve method will be much, much faster.
_______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
