MathAlgorithmaka integer factorization, trial division, factor with SPF

Prime Factorization

Decompose n into prime powers by trial division up to sqrt(n), or in O(log n) per query using a precomputed smallest-prime-factor table.

▶ Visualize Pattern: Math & Number Theory Practice (2)

Progress

Overview

Every integer n ≥ 2 is a unique product of primes: 360 = 2³ · 3² · 5. Trial division finds it by dividing out each candidate d = 2, 3, 4, … while d² ≤ n; whatever remains above 1 at the end is a prime. Cost O(√n), fine for a single n ≤ 10^12.

With a smallest-prime-factor sieve (see Sieve of Eratosthenes) each factorization is O(log n): repeatedly divide n by spf[n]. This is the tool when thousands of numbers up to 10^7 must be factored.

The factorization unlocks divisor counting (Π (e_i + 1)), divisor sums (Π (p^(e+1) - 1)/(p - 1)), Euler's totient (n · Π (1 - 1/p)), and GCD (Euclidean Algorithm)/LCM (Least Common Multiple) via per-prime min/max exponents.

primesfactorizationtrial divisionSPFO(sqrt n)divisors

Intuition

A mental model before the formal terms.

Peeling an onion: keep pulling off the smallest layer that comes away cleanly. Pull 2 off 360 as many times as it divides (three times, leaving 45), then 3 (twice, leaving 5). Once the remaining core is smaller than the square of the next layer size, the core itself must be a single prime — no two factors ≥ d could multiply to something below d².

How it works

Trial division: for d from 2 while d·d ≤ n: while n mod d == 0, record d and set n = n / d. After the loop, if n > 1, record n.
Speedup: handle d = 2 separately, then only test odd d (halves the work); or test only primes from a small sieve up to √n.
SPF: while n > 1: p = spf[n]; count how many times p divides n, dividing each time; record (p, count).
Divisor enumeration: from the factor list, generate all products Π p_i^(k_i) with 0 ≤ k_i ≤ e_i by nested loops or recursion.

Why it works

Because factors are removed in increasing order, when d divides n no smaller number does, so d is prime — composites have already been stripped via their own prime factors.

If n > 1 after the loop, all its prime factors are > √(original remaining n). Two such factors would multiply to more than n, so exactly one remains, and it is prime.

SPF correctness follows from the sieve's guarantee that spf[x] is the smallest prime dividing x; dividing it out repeatedly enumerates the factors in increasing order. Each division at least halves n, hence O(log n) steps.

Recognition

How to tell a problem wants this.

"Number of divisors", "sum of divisors", "distinct prime factors", "is n a perfect power".
Problems on gcd/lcm of many numbers, or "count elements sharing a prime factor" (union-find over primes).
Constraints with n ≤ 10^12 and one number (trial division) versus 10^5 numbers ≤ 10^6 (SPF).

“modulo 10^9 + 7” → Math & Number Theory

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Sieve of Eratosthenes visualization.

n — Integer between 10 and 60

1/30List every number from 2 to 30, all assumed prime. We only need to sieve with p up to sqrt(30) ≈ 5, because any composite ≤ n has a factor that small.

Current prime pMultiple being crossed outComposite (crossed out)Prime

PseudocodeLearn Sieve of Eratosthenes →

1isPrime = [true] * (n + 1)
2for p in 2 .. floor(sqrt(n)):
3  if isPrime[p]:
4    for m in p*p, p*p+p, .. n:
5      isPrime[m] = false
6primes = [p for p in 2..n if isPrime[p]]

Variables

n30

limit5

Complexity

best O(n)

avg O(n log log n)

worst O(n log log n)

space O(n)

Speed

Pseudocode

1factor(n):
2  factors = []
3  d = 2
4  while d * d <= n:
5    while n mod d == 0: factors.append(d); n = n / d
6    d += 1
7  if n > 1: factors.append(n)
8  return factors
9factor_spf(n): while n > 1: p = spf[n]; record p; n = n / p

Implementations

1import math
2 
3 
4def factorize(n: int) -> list[tuple[int, int]]:
5    """Trial division up to sqrt(n): every composite has a factor at or below
6    its square root, so the loop stops there and whatever remains is prime."""
7    out: list[tuple[int, int]] = []
8 
91 · Peel off 2 first so the loop can then step by 2
10    twos = 0
11    while n % 2 == 0:
12        n //= 2
13        twos += 1
14    if twos:
15        out.append((2, twos))
16 
172 · Only odd divisors remain, and only up to sqrt(n)
18    d = 3
19    while d * d <= n:
20        count = 0
21        while n % d == 0:
22            n //= d
23            count += 1
24        if count:
25            out.append((d, count))
26        d += 2
27 
283 · Anything left above 1 is a prime larger than sqrt(original)
29    if n > 1:
30        out.append((n, 1))
31    return out
32 
33 
344 · With a smallest-prime-factor table, factorisation is O(log n) divisions
35def factorize_with_spf(n: int, spf: list[int]) -> list[tuple[int, int]]:
36    out: list[tuple[int, int]] = []
37    while n > 1:
38        p = spf[n]
39        count = 0
40        while n % p == 0:
41            n //= p
42            count += 1
43        out.append((p, count))
44    return out
45 
46 
475 · The divisor count follows straight from the exponents
48def divisor_count(factors: list[tuple[int, int]]) -> int:
49    total = 1
50    for _, e in factors:
51        total *= e + 1
52    return total

Walkthrough

n //= 2 is integer division; using /= would produce a float and break every subsequent % test.
Python integers are unbounded, so this factorises arbitrarily large numbers correctly — slowly, but never wrongly.
while d * d <= n with a manual d += 2 replaces the C-style for, since Python range cannot express a bound that shrinks during iteration.
if twos: and if count: use integer truthiness, which is idiomatic Python for "is non-zero".
for _, e in factors unpacks and discards the prime, since divisor_count only needs the exponents.

Complexity (this implementation)

time O(sqrt(n)) trial division; O(log n) with an SPF table · space O(log n) for the factor list; O(n) for the SPF table

Because integers are unbounded, the cost of each division grows with the size of n — the O(sqrt(n)) count is in operations, not constant-time steps.

Language notes

// is floor division and returns an int; / always returns a float and would silently break the algorithm past 2^53.
sympy.factorint(n) returns a {prime: exponent} dict and uses Pollard rho plus elliptic-curve methods for large inputs.
math.isqrt(n) would give an exact loop bound, though comparing d * d <= n avoids recomputing it as n shrinks.
Arbitrary-precision integers mean there is no overflow to guard against, at the cost of each operation scaling with the number of digits.

Common mistakes in this language

Using /= instead of //=, which turns n into a float and makes every later % test unreliable.
Writing for d in range(3, int(n ** 0.5) + 1, 2), which fixes the bound at the *original* n and does far more work than necessary.
Forgetting the trailing if n > 1 and dropping the largest prime factor.

Language differences that matter here

Integer division is the dividing line: Python needs // (and / silently returns a float), C++ / on integers already truncates, and JS/TS have only float division, exact just to 2^53.
Range: Python factorises arbitrarily large integers correctly; C++ tops out at 64 bits without GMP; JS/TS need BigInt past 2^53, which cannot mix with number.
Library escape hatches: sympy.factorint in Python and GMP in C++ handle inputs where trial division is hopeless; JS/TS have no standard equivalent.
The loop shape differs because Python range cannot express a bound that shrinks mid-loop, so the while d * d <= n form is mandatory there and merely idiomatic elsewhere.

Complexity

Best

O(log n)

Average

O(sqrt n)

Worst

O(sqrt n)

Space

O(log n)

Trial division is O(sqrt n) per number (worst when n is prime). With an SPF table of size O(N): O(N log log N) preprocessing, then O(log n) per query.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

One or a few numbers up to ~10^12 — trial division (optionally only over primes ≤ 10^6).
Many numbers bounded by ~10^7 — precompute SPF once.
Deriving divisor counts, divisor sums, totients, or per-prime exponents for gcd/lcm arguments.

Avoid it when

Numbers around 10^18 or larger: √n = 10^9 trial divisions is too slow; use Pollard rho with Miller–Rabin.
When only primality is needed for one number — Miller–Rabin answers without factoring.
When the SPF table would not fit (n > 10^8) — fall back to trial division with a prime list.

Alternatives

Sieve of Eratosthenes GCD (Euclidean Algorithm)

Common mistakes

Forgetting the final if n > 1 — loses the largest prime factor (e.g. 14 → only 2).
Looping d ≤ √n with a fixed √n computed before dividing: still correct, but slower; recompute against the shrinking n or use d * d <= n.
d * d overflowing 32-bit ints when n is near 2^31; use 64-bit d.
SPF lookup with n larger than the table.
Generating divisors with nested loops that recompute p^k by Math.pow on floats in JavaScript — accumulate integer powers instead.

Interview patterns

Largest Component Size by Common Factor: union every number with each of its prime factors.
Count divisors of every number up to n (SPF + multiplicativity) or of a single large n (trial division).
Check if n is a perfect power or "ugly number" (only factors 2, 3, 5) by dividing out allowed primes.
Number of trailing zeros of n! = exponent of 5 in n!, via Legendre's formula Σ n / 5^k.

Example problems

Number of Connected Componentsmedium Count Primesmedium

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related