1
$\begingroup$

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)
$\endgroup$
2
  • $\begingroup$ @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. $\endgroup$ Commented Sep 11, 2019 at 21:51
  • $\begingroup$ Because you did 3 first. $\endgroup$ Commented Feb 24, 2021 at 7:21

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .