Mathematical intuition behind this algorithm: prime factorization

algorithmsprime factorizationpython

I am working on the Euler Project archives. I used Trial Division to try to find the prime factorization of a large number, but learned it was very slow (all algorithms should run under 1 minute. Mine did not complete inside of 10 minutes). I finally broke down and looked at someone else's code, but I don't fully understand it.

For those who might not want to look at code, the algorithm works like this:

  1. Given a number $n$, count the number of times n = n/2 without resulting in a remainder. This gives you all the instances of 2 in
    the prime factorization.
  2. n must now be an odd number. Start dividing $n = n/i$ for i = $3, 5, 7, 9, …,\sqrt{n}$. For each division without a remainder, we count $i$ as a prime number. It is important to note that we divide $n/i$ for $i = 3$ until $n/3$ provides a remainder. Only then do we increment to $i = 5$.
  3. If $n > 2$ at this point, this is our last prime factor.

Now the step that I can't convince myself of is step 2.

My specific question: What guarantees that when we reach $i = 9$, that it doesn't divide evenly into $n$, resulting in 9 being incorrectly labelled as a prime factor?

The code pertaining to my specific question is commented in all CAPS below. 

def prime_factors(n):
 # Print the number of two's that divide n
    while n % 2 == 0:
        print(2)
        n = n / 2

    # n must be odd at this point
    # so a skip of 2 ( i = i + 2) can be used
    # HERE IS WHERE I GET CONFUSED. 3,5, AND 7 are PRIME,
    # BUT WHAT GUARANTEES THAT i NEVER REACHES 9, WHICH IS NOT PRIME?
    for i in range(3, int(math.sqrt(n)) + 1, 2):

        # while i divides n , print i ad divide n
        while n % i == 0:
            print(i)
            n = n / i

            # Condition if n is a prime
    # number greater than 2
    if n > 2:
        print(n)

Best Answer

You divided out all the factors of $3$ from $n$ by the time you reached $i=9$, so $n$ can no longer be divisible by $9$.

In general $n$ is divisible by $i$ if and only if it is divisible by all divisors of $i$. Within your algorithm, by the time the loop reaches a given number $i$, $n$ has been modified such that it is no longer divisible by any numbers strictly less than $i$. Therefore at this stage of the procedure, $n$ can only be divisible by $i$ if $i$ is prime.

Related Question