# Mathematical intuition behind this algorithm: prime factorization

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)

• @Ian and so when I reach i = 15, 25, the same (by previously dividing out all the factors of 3 and 5, etc.) Thanks, I knew it was simple and I just couldn't see it. – rocksNwaves Sep 11 '19 at 21:51
• Because you did 3 first. – steven gregory Feb 24 at 7:21

## 2 Answers

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.

Of course, $$i$$ will reach $$9$$ at some point. The important point is that if, at that point, your $$n$$ is divisible by $$9$$, then it was divisible by $$3$$ at all the previous steps, including when you decided to stop dividing by $$3$$ — but you made sure that then, it wasn’t divisible by $$3$$, so there is no chance that divisibility by $$3$$ appears in further iterations.