[Tutor] Prime Factorization Tool

[Robert Sjoblom]

> So you can roughly double the speed of your function by skipping even
> numbers other than two. Remember that 2 itself is prime, but any other
> multiple of 2 is not. Take that test outside of the loop, and then loop over
> every second number starting with 3.
>

So, if I understood this right, my function should look like this then:
def isprime(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    for x in range(2, round(sqrt(n))+1):
        if n % x == 0:
            return False
    else:
        return True

This works like expected, but I think my factorization function has a
really bad problem somewhere.
def factorization(n):
    factor = 2
    x = 3
    while True:
        if n % x == 0:
            if isprime(x):
                factor = x
                n = n // x
                if n == 1:
                    return factor
            else:
                return factor
        x += 2

factorization(100) brings the program into an infinite loop. Same for
200, 300, 400. It works on 1000, so there's something that's not right
in there.

Going through the code, this is what happens:

factorization() gets 100, it tests it against 3 and fails, and it
tests it against 5 and it works. 5 gets sent to isprime() which
confirms that it's a prime. Factor is set to 5. n is set to n // 5,
which is 20. The loop goes again, but since x is now 7 it will never
actually end.
The reason why it ends when factorization(1000) runs is because it
accidentally finds x = 25 and 5*25 = 200 (1000//5 = 200), thus ending
the loop.

I'm not sure how to fix that. Recursion? It obviously happens when the
answer is something like 2*2*5*5.
-- 
best regards,
Robert S.