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$ – rocksNwaves Sep 11 '19 at 21:51
  • $\begingroup$ Because you did 3 first. $\endgroup$ – steven gregory Feb 24 at 7:21
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.