[Tutor] Prime Factorization Tool

[Lie Ryan]

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.