Primes, Sieves and Prime Factorization

A prime has exactly two divisors, 1 and itself. Interviews need three tools around primes: testing one number (trial division up to the square root), listing all primes up to n (the sieve of Eratosthenes), and factorizing numbers (trial division, or a smallest-prime-factor table when there are many queries).

Intuition

Trial division. If n = a * b with a <= b, then a <= sqrt(n). So a composite number always has a divisor no larger than its square root, and checking d up to sqrt(n) is enough. Every prime above 3 has the form 6k - 1 or 6k + 1, so you can skip two thirds of the candidates.

Sieve of Eratosthenes. Instead of testing each number, cross out composites: for each prime p, mark p*p, p*p + p, ... as composite. Starting at p*p is safe because smaller multiples k*p with k < p were already crossed out by the prime factors of k. The total work is about n * (1/2 + 1/3 + 1/5 + ...) = O(n log log n), practically linear.

Smallest prime factor (linear sieve). Record for every x <= n its smallest prime factor spf[x]. Then any x factorizes in O(log x) steps by repeatedly dividing by spf[x]. The linear sieve fills the table so that each composite is written exactly once, by its smallest prime factor.

When to use it in interviews / OAs

• "Count the primes below n", "find the closest pair of primes in a range".
• Factorizations: grouping numbers by shared prime factors (often with union-find), counting distinct prime factors, divisor counts and sums.
• Many queries "factorize x" with all x <= 10^6: build the spf table once.
• Primality of a single number up to about 10^12: trial division is fast enough. (For full 64-bit inputs, Miller-Rabin is the standard tool and is beyond typical interviews.)

Template

def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n < 4:
        return True  # 2 and 3
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:  # every prime above 3 is 6k - 1 or 6k + 1
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True


def sieve(n: int) -> bytearray:
    # is_p[i] == 1 exactly when i is prime, for 0 <= i <= n
    is_p = bytearray([1]) * (n + 1)
    for i in range(min(2, n + 1)):
        is_p[i] = 0  # 0 and 1 are not prime
    p = 2
    while p * p <= n:
        if is_p[p]:
            is_p[p * p::p] = bytes(len(range(p * p, n + 1, p)))  # cross out multiples from p*p
        p += 1
    return is_p


def primes_up_to(n: int) -> list[int]:
    return [i for i, flag in enumerate(sieve(n)) if flag]

Slice assignment crosses out all multiples of p in one C-level operation, which keeps the Python sieve fast even for n = 10^7. A bytearray uses one byte per number; a Python list of booleans would use eight times more.

Factorization

def factorize(n: int) -> list[tuple[int, int]]:
    # trial division: [(prime, exponent), ...] in increasing order, n >= 2
    out = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            e = 0
            while n % d == 0:
                n //= d
                e += 1
            out.append((d, e))
        d += 1 if d == 2 else 2  # after 2, only odd candidates
    if n > 1:
        out.append((n, 1))  # the leftover is a prime larger than the square root
    return out


def smallest_prime_factor(n: int) -> list[int]:
    # spf[x] = smallest prime dividing x, for 2 <= x <= n (linear sieve)
    spf = [0] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if spf[i] == 0:  # nothing smaller divides i, so i is prime
            spf[i] = i
            primes.append(i)
        for p in primes:
            if p > spf[i] or i * p > n:
                break
            spf[i * p] = p  # p is the smallest prime factor of i * p
    return spf


def factorize_spf(x: int, spf: list[int]) -> list[tuple[int, int]]:
    out = []
    while x > 1:
        p, e = spf[x], 0
        while x % p == 0:
            x //= p
            e += 1
        out.append((p, e))
    return out

From a factorization p1^e1 * ... * pk^ek, the number of divisors is (e1 + 1) * ... * (ek + 1). To list the divisors themselves, pair each small divisor with its partner:

def divisors(n: int) -> list[int]:
    small, large = [], []
    d = 1
    while d * d <= n:
        if n % d == 0:
            small.append(d)
            if d != n // d:
                large.append(n // d)  # the partner above the square root
        d += 1
    return small + large[::-1]

Primes in a far-away range

To list primes in [lo, hi] with hi up to 10^12 but a short range (hi - lo up to about 10^6), sieve only that window using the primes up to sqrt(hi):

from math import isqrt


def segmented_primes(lo: int, hi: int) -> list[int]:
    lo = max(lo, 2)
    if lo > hi:
        return []
    is_p = bytearray([1]) * (hi - lo + 1)
    for p in primes_up_to(isqrt(hi)):
        start = max(p * p, (lo + p - 1) // p * p)  # first multiple of p in range, at least p*p
        is_p[start - lo::p] = bytes(len(range(start, hi + 1, p)))
    return [lo + i for i, flag in enumerate(is_p) if flag]

Complexity

Task	Time	Space
Primality by trial division	O(sqrt(n))	O(1)
Sieve of Eratosthenes up to n	O(n log log n)	O(n)
Linear sieve (spf table)	O(n)	O(n)
Factorize with spf	O(log x) per query	—
Factorize by trial division	O(sqrt(n))	O(log n)
Segmented sieve	O((hi - lo) log log hi + sqrt(hi))	O(hi - lo + sqrt(hi))

Common pitfalls

• 0 and 1 are not prime, and 2 is the only even prime.
• Loop bounds: use i * i <= n (integers), not i <= sqrt(n) with floating point, which can be off by one for large n.
• Forgetting the leftover factor: after trial division up to sqrt(n), a remaining n > 1 is itself a prime factor.
• Memory: a sieve up to 10^8 needs 100 MB even as a bytearray; check the limits before sieving, or switch to a segmented sieve.
• Starting the inner loop at 2p instead of p*p is correct but wastes time; starting below p*p is unnecessary, starting above it is wrong.
• Counting primes below n vs up to n: read carefully whether n itself counts.

Interview variations

• Count primes below n: sieve and count.
• Closest prime pair in a range: sieve up to the right end, scan adjacent primes.
• Largest component by common factor: union every number with its prime factors (spf table plus union-find).
• Distinct prime factors of a product: union of the factor sets.
• Four divisors, sum of divisors, numbers with exactly three divisors (squares of primes).
• Ugly numbers (only 2, 3 and 5 as factors): divide them out and check for 1.