Prime Factorization Explained — Trial Division, Smallest Prime Factor Sieve in O(log n) [LC 952, Amazon, Microsoft]

Algorithm Statement#

Given a positive integer $n$, return its prime factorization: the multiset of primes whose product equals $n$. Equivalently, find primes $p_1 \le p_2 \le \dots \le p_k$ with $n = p_1 \cdot p_2 \cdots p_k$.

Two regimes matter in interviews:

1. Single query, large $n$: factor $n$ up to $10^{12}$ in $O(\sqrt{n})$ via trial division.
2. Many queries, $n \le N$: precompute the smallest prime factor (SPF) for every value up to $N$, then factor each query in $O(\log n)$.

Constraints:

• $2 \le n \le 10^{12}$ for trial division.
• $2 \le n \le 10^7$ and up to $10^6$ queries for the sieve approach.

Example:

Input:  n = 360
Output: [2, 2, 2, 3, 3, 5]
Explanation: 360 = 2^3 * 3^2 * 5.

Why This Problem Matters#

Prime factorization unlocks dozens of LeetCode problems: LC 952 Largest Component Size by Common Factor, LC 1071 GCD of Strings, LC 1808 Maximize Number of Nice Divisors, LC 2521 Distinct Prime Factors of Product of Array. Amazon and Microsoft routinely lean on factorization questions because they test three skills at once: algorithmic thinking, number-theoretic intuition, and the ability to choose the right preprocessing for the query distribution.

The factorization is also the gateway to Euler's totient function, divisor counting, Mobius inversion, and the structure of multiplicative functions. Get this right and a wide swath of advanced number theory becomes routine.

The Core Insight#

The fundamental theorem of arithmetic says every integer $n \ge 2$ has a unique prime factorization (up to ordering). Two strategies exploit this differently.

Trial division. If $n$ is composite, it has at least one prime factor $\le \sqrt{n}$. Iterate $p = 2, 3, 4, \dots, \lfloor \sqrt{n} \rfloor$. Whenever $p$ divides $n$, append $p$ to the answer and divide $n$ by $p$ until it no longer divides. After the loop, if $n > 1$, the remaining $n$ is itself a prime factor (it must be, otherwise it would have been caught by some $p \le \sqrt{n}$). Total cost: $O(\sqrt{n})$ in the worst case (when $n$ is prime).

Smallest prime factor (SPF) sieve. Precompute, for every number $i$ up to $N$, the smallest prime that divides $i$. Build it like the Sieve of Eratosthenes: walk $p = 2, 3, 5, \dots$, and for every multiple of $p$ that does not yet have an SPF, set its SPF to $p$. To factor a query $n$, repeatedly divide by spf[n] until $n = 1$. Each division strictly reduces $n$ by a factor of at least 2, so the loop runs $O(\log n)$ times.

Why $\sqrt{n}$ works for trial division. Suppose $n = a \cdot b$ with $a \le b$. Then $a \le \sqrt{n}$ — otherwise the product would exceed $n$. So the smaller factor must lie below $\sqrt{n}$, and once we strip every prime $\le \sqrt{n}$, what remains is at most one prime (the larger of the two factors).

Visual Dry Run#

Factor $n = 84$ by trial division.

n = 84, p = 2
  84 % 2 == 0  → record 2, n = 42
  42 % 2 == 0  → record 2, n = 21
  21 % 2 != 0  → move on
 
p = 3
  21 % 3 == 0  → record 3, n = 7
  7  % 3 != 0  → move on
 
p = 4..sqrt(7) (no candidates)
 
Loop ends. n = 7 is greater than 1 → record 7.
 
Final factors: [2, 2, 3, 7].  Verify: 2*2*3*7 = 84.

Build the SPF sieve up to $N = 12$.

spf = [0, 0, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2]
 
p = 2: spf[2..12 step 2] set to 2 if 0
p = 3: spf[3], spf[9] set to 3
p = 5: spf[5] set to 5
p = 7: spf[7] set to 7
p = 11: spf[11] set to 11
 
Factor n = 12 with the SPF table:
  spf[12] = 2  → record 2, n = 6
  spf[6]  = 2  → record 2, n = 3
  spf[3]  = 3  → record 3, n = 1
  Done. Factors: [2, 2, 3].

Solution (Optimal)#

Python — Trial Division (single query)#

def prime_factorize(n: int) -> list[int]:
    factors = []
    p = 2
    while p * p <= n:
        while n % p == 0:
            factors.append(p)
            n //= p
        p += 1
    if n > 1:
        factors.append(n)
    return factors

Complexity: $O(\sqrt{n})$ time, $O(\log n)$ space for the factor list (since at most $\log_2 n$ factors fit).

Python — SPF Sieve (many queries)#

def build_spf(N: int) -> list[int]:
    spf = list(range(N + 1))           # spf[i] = i initially
    for p in range(2, int(N**0.5) + 1):
        if spf[p] == p:                # p is prime
            for multiple in range(p * p, N + 1, p):
                if spf[multiple] == multiple:
                    spf[multiple] = p
    return spf
 
def factorize_with_spf(n: int, spf: list[int]) -> list[int]:
    factors = []
    while n > 1:
        factors.append(spf[n])
        n //= spf[n]
    return factors

Complexity: $O(N \log \log N)$ to build the sieve, $O(\log n)$ per query, $O(N)$ space.

JavaScript — Trial Division#

function primeFactorize(n) {
    const factors = [];
    for (let p = 2; p * p <= n; p++) {
        while (n % p === 0) {
            factors.push(p);
            n = Math.floor(n / p);
        }
    }
    if (n > 1) factors.push(n);
    return factors;
}

JavaScript — SPF Sieve#

function buildSPF(N) {
    const spf = Array.from({ length: N + 1 }, (_, i) => i);
    for (let p = 2; p * p <= N; p++) {
        if (spf[p] === p) {
            for (let m = p * p; m <= N; m += p) {
                if (spf[m] === m) spf[m] = p;
            }
        }
    }
    return spf;
}
 
function factorizeWithSPF(n, spf) {
    const factors = [];
    while (n > 1) {
        factors.push(spf[n]);
        n = Math.floor(n / spf[n]);
    }
    return factors;
}

Common Mistakes#

1. Iterating to $n$ instead of $\sqrt{n}$. Trial division should stop at p * p > n. Going further is a quadratic blowup.
2. Forgetting the leftover prime. After the loop ends, if $n > 1$ then the remaining value is itself a prime factor. Skipping this step misses primes greater than the original $\sqrt{n}$.
3. Off-by-one in the SPF sieve. When $p$ is prime, the inner loop must start at $p \cdot p$ and only set spf[multiple] if it has not yet been assigned.
4. Storing duplicate primes when you wanted unique ones. If the question asks for the set of distinct primes, deduplicate or use a set.
5. Floating-point square roots in C++. Use p * p <= n as a 64-bit integer check, not p <= sqrt(n), which can suffer from rounding issues.
6. Building the sieve too large. For $N = 10^7$ in Python, the sieve takes about 80 MB. Use a NumPy array or a smaller primitive type if memory matters.

Interview Tips#

• Ask: "Single query or many queries?" The answer determines the algorithm.
• Ask the upper bound on $n$. For $n \le 10^{12}$, trial division is fine. For $n$ up to $10^{18}$, you need Pollard rho.
• If the modulus appears (for example, counting divisors mod prime), mention that the multiplicative structure of $n$ lets you compute $\tau(n)$ as $\prod (e_i + 1)$ without enumerating divisors.
• For "find largest prime factor of $n$" (Project Euler classic), the trial-division loop above runs in $O(\sqrt{n})$ — and the leftover value at the end is the largest prime factor.

Follow-up Questions#

Q1: Count the number of distinct prime factors of $n$ for $n$ up to $10^7$. A: Build the SPF sieve and walk the factorization, deduplicating consecutive equal factors. Or precompute a separate omega[n] array.

Q2: Find the number of divisors of $n$. A: Factor $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$. The divisor count is $\tau(n) = \prod_{i=1}^{k}(e_i + 1)$.

Q3: Pollard rho for $n$ up to $10^{18}$. A: Use Pollard's rho algorithm with a Miller-Rabin primality precheck. Expected time per factor is $O(n^{1/4})$.

Q4: Sum of all proper divisors of $n$. A: Compute $\sigma(n) = \prod \frac{p_i^{e_i+1} - 1}{p_i - 1}$, then subtract $n$ itself.

Key Takeaways#

• Trial division factors a single $n$ in $O(\sqrt{n})$; remember to capture the leftover prime after the loop.
• SPF sieve prepares all values up to $N$ in $O(N \log \log N)$ and answers each query in $O(\log n)$.
• The fundamental theorem of arithmetic guarantees a unique prime factorization — the multiplicative structure powers totient, divisor count, and Mobius computations.
• For $n \le 10^7$, the SPF sieve is the standard preprocessing; for $n$ up to $10^{18}$, switch to Pollard rho.
• Cache the factorization when the same value appears repeatedly — Amazon's interviewers love seeing memoization on top of number theory.
• Divisor count and divisor sum follow directly from the factorization, so always factor first when an interview problem hints at multiplicative behavior.