Re: [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.

_______________________________________________
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor