18.9 Factorization

Many number-theoretic algorithms become simpler once a number is expressed as a product of primes. Divisor counting, divisor sums, Euler's phi function, modular arithmetic, primality testing, cryptography, and multiplicative functions all rely on prime factorization.

The Fundamental Theorem of Arithmetic states that every integer greater than one can be represented uniquely as a product of prime powers. Factorization algorithms exploit this fact by repeatedly discovering prime divisors and reducing the remaining problem.

This section develops practical factorization techniques, beginning with trial division and progressing toward sieve-assisted methods suitable for repeated queries.

Problem

Given a positive integer:

compute its prime factorization.

Examples:

84 = 2² × 3 × 7

360 = 2³ × 3² × 5

1001 = 7 × 11 × 13

The output should identify both the prime factors and their exponents.

The Fundamental Theorem of Arithmetic

Every integer:

n > 1

can be written uniquely as:

n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ

where:

each pᵢ is prime
each exponent eᵢ is positive
the primes are distinct

Example:

360 = 2³ × 3² × 5¹

No other prime-power decomposition exists.

This uniqueness property allows many arithmetic functions to be computed directly from the factorization.

Trial Division

The simplest factorization algorithm repeatedly tests divisibility.

def factorize(n):
    factors = []

    d = 2

    while d * d <= n:
        count = 0

        while n % d == 0:
            n //= d
            count += 1

        if count > 0:
            factors.append((d, count))

        d += 1

    if n > 1:
        factors.append((n, 1))

    return factors

Example:

print(factorize(84))

Output:

[(2, 2), (3, 1), (7, 1)]

representing:

84 = 2² × 3 × 7

Why the Algorithm Works

Suppose:

n = p × m

and p is the smallest prime factor.

Removing all copies of p yields:

which is smaller than the original number.

Repeating the process eventually removes every prime factor.

The algorithm terminates because each successful division reduces the remaining value.

Example Walkthrough

Factor:

Start with:

Divide by 2 repeatedly:

360 → 180 → 90 → 45

Therefore:

2³

remains in the factorization.

Current remainder:

Divide by 3 repeatedly:

45 → 15 → 5

Therefore:

3²

appears.

Current remainder:

Since:

is prime:

5¹

appears.

Final result:

360 = 2³ × 3² × 5

Using the Square Root Bound

The factorization algorithm stops at:

√n

for the same reason used in primality testing.

If:

n = a × b

and both factors exceed:

√n

then:

ab > n

which is impossible.

Therefore every composite number has a factor less than or equal to its square root.

Once the search exceeds:

√n

the remaining value is either:

1
a prime

No further work is required.

Skipping Even Divisors

A small optimization eliminates unnecessary checks.

def factorize(n):
    factors = []

    count = 0

    while n % 2 == 0:
        n //= 2
        count += 1

    if count:
        factors.append((2, count))

    d = 3

    while d * d <= n:
        count = 0

        while n % d == 0:
            n //= d
            count += 1

        if count:
            factors.append((d, count))

        d += 2

    if n > 1:
        factors.append((n, 1))

    return factors

Only odd divisors remain after removing factors of two.

Complexity

Trial division requires testing divisors up to:

√n

Time complexity:

O(√n)

Space complexity:

O(1)

For a single moderate-sized number, this is often sufficient.

For repeated factorization queries, preprocessing becomes attractive.

Smallest Prime Factor Tables

Suppose we need to factor thousands or millions of numbers.

Instead of recomputing divisors repeatedly, precompute the smallest prime factor of every number.

Example SPF table:

Number	SPF
2	2
3	3
4	2
5	5
6	2
7	7
8	2
9	3

A factorization then becomes repeated table lookup.

def factorize_spf(n, spf):
    factors = []

    while n > 1:
        p = spf[n]
        count = 0

        while n % p == 0:
            n //= p
            count += 1

        factors.append((p, count))

    return factors

Example:

print(factorize_spf(360, spf))

Output:

[(2, 3), (3, 2), (5, 1)]

Factorization from a Linear Sieve

The linear sieve introduced in the previous section naturally computes smallest prime factors.

Once the SPF array exists:

Preprocessing:
O(n)

Single factorization:
O(log n)

This is significantly faster than trial division when many queries are required.

Counting Divisors

Once the factorization is known:

n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ

the number of divisors is:

(e₁ + 1)(e₂ + 1)...(eₖ + 1)

Example:

360 = 2³ × 3² × 5¹

Therefore:

(3+1)(2+1)(1+1)
=
4×3×2
=
24

The number 360 has 24 divisors.

Factorization turns a difficult counting problem into a simple multiplication.

Sum of Divisors

For:

n = p^e

the divisor sum is:

1 + p + p² + ... + p^e

For a general factorization:

n = p₁^e₁ × ... × pₖ^eₖ

the divisor sum becomes:

(1+p₁+\cdots+p₁^e₁)
(1+p₂+\cdots+p₂^e₂)
...
(1+pₖ+\cdots+pₖ^eₖ)

Example:

12 = 2² × 3

Divisor sum:

(1+2+4)(1+3)
=
7×4
=
28

Verification:

1+2+3+4+6+12
=
28

Largest Prime Factor

Sometimes we need only the largest prime factor.

def largest_prime_factor(n):
    largest = 1

    d = 2

    while d * d <= n:
        while n % d == 0:
            largest = d
            n //= d

        d += 1

    if n > 1:
        largest = n

    return largest

Example:

print(largest_prime_factor(13195))

Output:

This pattern appears in many numerical problems.

Detecting Perfect Powers

Factorization also reveals whether:

n = a^k

for some integer:

k > 1

Example:

64 = 2⁶

Factorization:

2⁶

Exponent GCD:

gcd(6)=6

Since the exponent GCD exceeds 1, the number is a perfect power.

Similarly:

216 = 2³ × 3³

Exponent GCD:

gcd(3,3)=3

Therefore:

216 = 6³

Applications

Divisor Functions

Counting divisors and divisor sums rely entirely on prime factorization.

Cryptography

RSA security depends on the difficulty of factoring large semiprimes.

Rational Arithmetic

Fraction simplification uses common prime factors.

Number Theory

Many arithmetic functions derive directly from factorization.

Competitive Programming

Numerous problems reduce to exponent manipulation within prime decompositions.

Algebra

Prime-power decomposition underlies many structural theorems.

Common Mistakes

Continuing Past √n

Once:

d × d > n

the remaining value is either 1 or prime.

Further searching is unnecessary.

Forgetting the Remaining Prime

Consider:

After removing:

the remaining value is:

The algorithm must append that final prime.

Recomputing Factorizations

Repeated trial division becomes expensive.

Use an SPF table when many queries are expected.

Ignoring Multiplicities

Recording only distinct primes loses important information.

For example:

72 = 2³ × 3²

requires both exponents.

Testing

def test_factorization():
    assert factorize(2) == [(2, 1)]

    assert factorize(12) == [
        (2, 2),
        (3, 1),
    ]

    assert factorize(360) == [
        (2, 3),
        (3, 2),
        (5, 1),
    ]

A useful validation strategy is reconstructing the original number from the factorization.

def reconstruct(factors):
    result = 1

    for p, e in factors:
        result *= p ** e

    return result

The reconstructed value should equal the original input.

Takeaway

Prime factorization decomposes an integer into its unique product of prime powers. Trial division provides a simple O(√n) solution for individual values, while sieve-based smallest-prime-factor tables support fast repeated factorization. Once a factorization is available, many seemingly difficult tasks become straightforward, including divisor counting, divisor sums, perfect-power detection, arithmetic-function computation, and numerous algorithmic number-theory problems. The next sections build directly on this prime-power representation.