[Tutor] Prime Factorization Tool

[Robert Sjoblom]

> Well, there are really only a couple of optimizations that you could make.
> That's the nice (bad?) thing about primes - you really only *can* brute
> force a solution. That's why nice things like encryption exist.
Yes, I know that; perhaps I was unclear but my issues with brute force
are for solutions 1 and 2, not solution 3. For instance, problem 2 is:
#By considering the terms in the Fibonacci sequence whose
#values do not exceed four million, find the sum of the even-valued terms.

And my solution is
def fib(n = 4000000):
    a, b = 0, 1
    while a < n:
        a, b = b, a + b
        if a%2 == 0: yield a

Which is perfectly fine as a solution, but nowhere near as elegant as
the mathematical solution. Anyway, I digress.

> The less obvious optimization is in reference to primes - you don't actually
> have to check all the way up to N. Or even N/2. You only have to check
> numbers up to the square root of N. This explanation may not be
> mathematically sound, but basically the reason this works is the definition
> of prime: N is divisible only by N and 1. If you divide a number by 2 then
> then the result will be the largest factor (e.g. 100/2 = 50). But as you
> start increasing the divisor then obviously the result has to decrease. The
> point at which these numbers are equivalent? The square root, of course.
I was suspecting there was something like that; my thoughts were
starting to move toward something along those lines. I suppose I'm
just rusty.


> Now, I'm not sure what the time complexity of these two operations is, but
> go ahead and put this line in your isprime:
>
> if n == 11: print("Checked 11... again")
>
> Can you think of a way to compute the primes you need to check only once?
First reaction: "whoa!". That is a lot of redundant calculations. I'm
afraid I'm a bit stumped on this one; one solution that seems to work
is sending the factor to isprime() along with n, and do the for loop
like this:
for x in range(factor, round(sqrt(n))):
But I'm not sure that's actually a good idea or if it just happened to
work in this particular case. As I said, it seems to work but it could
just be a coincidence. Way I see it, I've already tested all the
numbers up to the last factor and so I shouldn't need to test them
again? However, your "if n == 11" line confuses me; after the changes
I never once hit n == 11, which is weird?

Anyway, this is my reworked functions, which are much faster than the
original ones. I really need to learn how to use the timeit module to
see the difference.

from math import sqrt

def isprime(n, factor):
    if n == 1:
        return False
    for x in range(2, round(sqrt(n))):
        if n % x == 0:
            return False
    else:
        return True

def factorization(n):
    factor = 2
    x = 3
    while True:
        if n % x == 0:
            if isprime(x, factor):
                factor = x
                n = n // x
                if n == 1:
                    return factor
            else:
                return factor
        x += 2
print(factorization(600851475143))





>
> HTH,
> Wayne



-- 
best regards,
Robert S.