Factorization

Computing a full prime factorization \(n = p_1 p_2 \cdots p_k\) involves a little more work than finding a single divisor.

Trial Division

The most direct way to factor \(n\) is trial division: try dividing by each candidate \(d = 2, 3, 4, \ldots\) in turn, and whenever \(d\) divides evenly, record it and divide it out. Starting from \(m = n\) and \(d = 2\), repeat the following update until \(m = 1\):

\[\begin{split} (m, d) \;\longmapsto\; \begin{cases} (m / d,\ d) & \text{if } d \mid m, \\[4pt] (m,\ d + 1) & \text{if } d \nmid m. \end{cases} \end{split}\]

Each time the first case applies, \(d\) is a prime factor of \(n\). The candidate \(d\) only advances once it fails to divide \(m\), which catches repeated factors. For example, factoring \(n = 20\) proceeds as follows.

\[\begin{split} \begin{aligned} (20, 2) &\longmapsto (10, 2) && \text{since } 2 \mid 20 \\ (10, 2) &\longmapsto (5, 2) && \text{since } 2 \mid 10 \\ (5, 2) &\longmapsto (5, 3) && \text{since } 2 \nmid 5 \\ (5, 3) &\longmapsto (5, 4) && \text{since } 3 \nmid 5 \\ (5, 4) &\longmapsto (5, 5) && \text{since } 4 \nmid 5 \\ (5, 5) &\longmapsto (1, 5) && \text{since } 5 \mid 5 \end{aligned} \end{split}\]

Collecting \(d\) from each step where the first case applied gives \(20 = 2 \cdot 2 \cdot 5\).

Problem 2

Write a function named factor_brute() that accepts a positive integer \(n\). Compute the prime factorization of \(n\) by trial division:

  1. Start with the candidate divisor \(d = 2\).

  2. If \(d\) divides \(n\), record \(d\) and replace \(n\) with \(n / d\). Otherwise, increase \(d\) by \(1\).

  3. Repeat step 2 until \(d > n\).

Return a list of the recorded prime factors, with repetition, in increasing order.

Reminder: Floor division // keeps \(n / d\) an integer.

Test Cases

print(factor_brute(60))
print(factor_brute(97))
print(factor_brute(1024))
[2, 2, 3, 5]
[97]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Recursive Strategy

Because prime factorizations are unique, they admit a recursive structure: if \(n = dp\) where \(p\) is prime, then the prime factorization for \(n\) is \(p\) times the prime factorization for \(d\). For example,

\[ 20 = 2 \cdot 10 = 2 \cdot (2 \cdot 5) = 2 \cdot 2 \cdot 5. \]

That is, the prime factorization for \(20\) is \(2\) times the prime factorization for \(10\).

Recursion can provide a faster prime factorization algorithm than trial division. For instance, if \(n\) itself is prime, no candidate divides it, so trial division checks every integer up to \(n\). However, a search that reaches \(d^2 > n\) without finding a factor has shown that \(n\) is prime. To apply this bound at every step, peel off one factor at a time and factor what remains.

  • Base case: if \(n = 1\), there are no prime factors.

  • Recursive case: search for the smallest \(d \ge 2\) with \(d^2 \le n\) that divides \(n\).

    • If such a \(d\) exists, it is prime, and the prime factors of \(n\) are \(d\) followed by the prime factors of \(n / d\).

    • If no such \(d\) exists, then \(n\) is prime, so its only prime factor is \(n\) itself.

Each search only runs up to the square root of the remaining number, which shrinks as factors are divided out. For example, factoring \(84\) proceeds as follows.

\[\begin{split} \begin{aligned} 84 &= 2 \cdot 42 && \text{since } 2 \mid 84 \\ &= 2 \cdot 2 \cdot 21 && \text{since } 2 \mid 42 \\ &= 2 \cdot 2 \cdot 3 \cdot 7 && \text{since } 2 \nmid 21 \text{ and } 3 \mid 21 \end{aligned} \end{split}\]

The search on \(7\) finds no factor, since \(2 \nmid 7\) and \(3^2 = 9 > 7\), so \(7\) is prime and the recursion stops.

Problem 3

Write a function named factor_recursive() that accepts a positive integer \(n\). Compute the prime factorization of \(n\) recursively:

  1. If \(n = 1\), there are no prime factors. In this case, return an empty list [].

  2. Otherwise, search for the smallest integer \(d \ge 2\) with \(d^2 \le n\) that divides \(n\).

  3. If such a \(d\) exists, the prime factors of \(n\) are \(d\) followed by the prime factors of \(n / d\).

  4. If no such \(d\) exists, then \(n\) is prime.

Return a list of the prime factors of \(n\), with repetition, in increasing order.

Hint: List addition performs concatenation; for example, [1, 2] + [3] evaluates to [1, 2, 3].

Test Cases

print(factor_recursive(60))
print(factor_recursive(97))
print(factor_recursive(1024))
[2, 2, 3, 5]
[97]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]

Speed Comparison

The following code times factor_brute() and factor_recursive() on a few inputs.

import time

for n in [1024, 999983, 99999989]:
    start = time.time()
    factor_brute(n)
    middle = time.time()
    factor_recursive(n)
    end = time.time()

    print("n =", n)
    print("  brute force:", round(middle - start, 4), "seconds")
    print("  recursive:", round(end - middle, 4), "seconds")
n = 1024
  brute force: 0.0 seconds
  recursive: 0.0 seconds
n = 999983
  brute force: 0.0364 seconds
  recursive: 0.0 seconds
n = 99999989
  brute force: 2.5438 seconds
  recursive: 0.0004 seconds

The results may vary from computer to computer, but for these inputs, the recursive approach becomes much faster as \(n\) grows.