Prime Factorization Algorithm: Break Any Number Into Primes in O(√n)

You haven't needed to factor a number since 9th grade. Then you walk into a coding interview and someone asks you about ugly numbers, or the minimum keystrokes to type exactly 18 'A's, and suddenly you're wishing you'd paid more attention in math class.

The algorithm is short. The reasoning is worth understanding. And the d * d <= n condition is almost guaranteed to come up as a follow-up.

Every Integer Has a Fingerprint

The Fundamental Theorem of Arithmetic says every integer greater than 1 can be written as a unique product of primes. Not just a product. The product. No other combination of primes multiplies to the same number.

Take 360:

360 = 2 × 2 × 2 × 3 × 3 × 5
    = 2³ × 3² × 5¹

No other combination of primes gives you 360. Which is probably why mathematicians called this the "Fundamental Theorem" instead of "that neat trick with numbers."

Every integer is a molecule of primes. That uniqueness is what makes factorization useful: it lets you reason about divisibility, GCD, LCM, and divisor counts in a deterministic way. Once you have the prime factors, a lot of number theory problems reduce to simple arithmetic on exponents.

The Loop That Eats Factors

The standard approach is trial division: repeatedly divide by the smallest factor you can find, collecting primes as you go.

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

That's the whole thing. Two while loops and a trailing check. You've written more code than this to handle a 404 response.

Walk through it with 360:

d = 2: divide out three times. Collected [2, 2, 2]. Now n = 45.
d = 3: divide out twice. Collected [3, 3]. Now n = 5.
d = 4: 4 * 4 = 16 > 5. Loop exits.
n = 5 > 1, so append 5.

Result: [2, 2, 2, 3, 3, 5]. Correct.

Trial division of 360 step by step

The key insight is the loop condition d * d <= n. If n = a × b and both a > √n and b > √n, their product would exceed n. Contradiction. So at least one factor must be at or below √n. Once the outer loop exits, any remaining n > 1 is necessarily prime.

One more thing worth knowing: you never need to check whether d itself is prime. If d = 6 comes along, n has already been divided by 2 and 3. So n % 6 == 0 will never fire. The inner while loop gives you prime-only divisors for free.

What Does That Buy You?

Time: O(√n). The outer loop runs at most √n iterations. The inner loop doesn't compound this because each division strictly reduces n. Worst case is a prime input: the loop grinds all the way to √n finding nothing, then the trailing if n > 1 check catches it at the end.

Space: O(log n). The maximum number of prime factors, counting multiplicity, is log₂(n). A 64-bit integer has at most 63 factors of 2. In practice the list is tiny. Nobody is going to give you a number with 60 prime factors in a 45-minute interview.

Store It as a Map for Interview Problems

A flat list is fine for some problems. For most, you want {prime: exponent} pairs:

from collections import defaultdict

def prime_factor_map(n: int) -> dict[int, int]:
    factors = defaultdict(int)
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] += 1
            n //= d
        d += 1
    if n > 1:
        factors[n] += 1
    return dict(factors)

prime_factor_map(360) returns {2: 3, 3: 2, 5: 1}. Once you have this form, divisor counting and LCM become one-liners.

Where This Actually Shows Up

Counting Divisors

If n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ, the number of divisors is:

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

For 360 = 2³ × 3² × 5¹: (3+1)(2+1)(1+1) = 24 divisors. This gets you the answer in O(√n) instead of the O(n) approach that checks every integer up to n one by one.

Why does the formula work? Each divisor picks some subset of each prime's exponents. For the prime 2³, a divisor can include 2⁰, 2¹, 2², or 2³, giving 4 choices. Multiply the choices for each prime and you get the total count.

Least Common Multiple

For each prime, GCD takes the minimum exponent and LCM takes the maximum:

360 = 2³ × 3² × 5
84  = 2² × 3  × 7

GCD(360, 84) = 2² × 3¹ = 12
LCM(360, 84) = 2³ × 3² × 5 × 7 = 2520

In practice you use the Euclidean algorithm for GCD because it's O(log n) and requires no factorization. But the formula lcm(a, b) = a × b / gcd(a, b) falls directly out of this max/min exponent logic. Understanding why makes the formula obvious rather than something you memorize and pray you remember under pressure.

The 2 Keys Keyboard Problem (LeetCode 651)

Here is a problem that will fool you if you've been grinding DP.

You start with one 'A'. Each operation is either "copy all" or "paste." Find the minimum operations to reach exactly n 'A's.

Most people see this and immediately reach for DP. That is the wrong move.

The insight: the answer is the sum of prime factors of n, counting multiplicity. For n = 12 = 2² × 3, that's 2 + 2 + 3 = 7 operations. What looks like a DP problem is a factorization problem in disguise. If you see it, you write a 10-line solution while other candidates are debugging their 2D tables.

This is also the kind of problem where naming the insight matters. "The optimal strategy mirrors the prime factorization of n" is the sentence that moves you from "correct" to "impressive."

Ugly Numbers

An ugly number's only prime factors are 2, 3, and 5. Checking is mechanical: divide them all out and see if anything remains.

def is_ugly(n: int) -> bool:
    if n <= 0:
        return False
    for p in [2, 3, 5]:
        while n % p == 0:
            n //= p
    return n == 1

Ugly Number II (LeetCode 264) asks for the nth ugly number, which calls for a min-heap approach. But recognizing that the definition is purely a constraint on prime factors is the first step either way.

Halve the Work with One Trick

Handle 2 separately, then step by 2. You skip every even candidate:

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

Still O(√n), but roughly half the iterations in practice. For n up to 10^9, that's at most about 31,623 checks. Fast enough for any reasonable interview input.

If you need to factorize many numbers up to N, precompute the smallest prime factor for each using a sieve. Then each factorization becomes O(log n) by following the smallest-prime-factor chain down.

What to Say When You Write This

When prime factorization is the right tool, say so: "I want to express n as a product of primes, which I can do in O(√n) with trial division." Then write the loop. Don't silently produce correct code and hope the interviewer fills in the blanks.

Interviewers almost always probe the d * d <= n condition. They've seen enough candidates write d <= n by accident that it's become a standard follow-up. Have your answer ready: "Once d exceeds the square root of the current n, any remaining factor must itself be prime, because every smaller factor has already been divided out."

Name the edge cases before being asked. n = 1 has no prime factors. If n is prime, the loop exits without dividing once, and the trailing check catches it. If you wait to be prompted on edge cases, you're giving away points you could have kept.

That combination, articulating the bound and surfacing edge cases unprompted, is what separates "technically correct" from "strong hire." Knowing the algorithm is table stakes. Explaining it clearly while you code is the signal interviewers are actually writing down. If you want to practice delivering that kind of reasoning under real interview pressure, SpaceComplexity runs voice-based mock interviews with rubric-based feedback on exactly this kind of problem.