Prime Numbers: Sieve of Eratosthenes, Trial Division, Miller-Rabin

Prime Numbers: Sieve of Eratosthenes, Trial Division, and the Miller-Rabin Test

Prime number problems appear at FAANG interviews, fintech screens, and competitive programming. The two foundational tasks are: (1) check whether a single number is prime, and (2) find all primes up to N. Each has a classic algorithm — trial division for the first, Sieve of Eratosthenes for the second — and several optimizations and variants. This guide covers the standard approaches with working code, when to use each, and the variations interviewers ask as follow-ups.

Problem 1: Check Whether a Single Number Is Prime

Approach: Trial Division (Standard Answer)

Test divisibility by all integers from 2 up to sqrt(n). If any divides n, n isn’t prime.

def is_prime(n: int) -> bool:
    """O(sqrt(n)) time, O(1) space."""
    if n < 2:
        return False
    if n < 4:
        return True  # 2 and 3
    if n % 2 == 0:
        return False
    # Only test odd divisors from 3
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True


# Tests
print(is_prime(1))    # False
print(is_prime(2))    # True
print(is_prime(17))   # True
print(is_prime(100))  # False
print(is_prime(997))  # True

Complexity: O(√n) time, O(1) space.

Why √n? If n has a divisor d > √n, then n / d is a divisor < √n. So if no divisor exists below √n, no divisor exists at all — n is prime.

Optimization: 6k ± 1

Every prime > 3 has the form 6k ± 1 (others are divisible by 2 or 3). Testing only these candidates skips two-thirds of the work.

def is_prime_6k(n: int) -> bool:
    """Optimized trial division using 6k ± 1 form."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

Same complexity, smaller constant factor. Worth knowing for competitive-programming-flavored interviews.

Problem 2: Find All Primes Up to N

Approach: Sieve of Eratosthenes (Standard Answer)

Mark all composites up to N. Start at 2; mark every multiple of 2 as composite. Move to the next unmarked number; mark its multiples; repeat.

def sieve_of_eratosthenes(n: int) -> list[int]:
    """O(n log log n) time, O(n) space."""
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            # Start marking from i*i (smaller multiples already marked)
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


# Test
print(sieve_of_eratosthenes(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Complexity: O(n log log n) time, O(n) space.

Why start marking from i² rather than 2i? Multiples 2i, 3i, …, (i-1)i have already been marked by smaller primes. Starting at i² is the first multiple of i not yet marked, saving roughly half the work.

Optimization: Linear Sieve

O(n) time using each composite exactly once. More complex to implement; useful for n > 10⁷ where the log log factor matters.

def linear_sieve(n: int) -> list[int]:
    """O(n) time."""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    primes = []
    smallest_prime = [0] * (n + 1)
    for i in range(2, n + 1):
        if is_prime[i]:
            primes.append(i)
            smallest_prime[i] = i
        for p in primes:
            if p > smallest_prime[i] or i * p > n:
                break
            is_prime[i * p] = False
            smallest_prime[i * p] = p
    return primes

Each composite is marked by its smallest prime factor exactly once, giving O(n) total marking operations.

Problem 3: Probabilistic Primality (Miller-Rabin)

For very large n (cryptographic sizes — 1024+ bits), trial division is too slow even at O(√n). The Miller-Rabin test runs in O(k log³ n) where k is the number of rounds, with error probability ≤ 4^(-k).

import random

def miller_rabin(n: int, k: int = 20) -> bool:
    """Probabilistic primality test. Error <= 4^(-k)."""
    if n < 2:
        return False
    if n in (2, 3):
        return True
    if n % 2 == 0:
        return False

    # Write n-1 as 2^r × d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

For interview purposes, mention Miller-Rabin if the interviewer asks about cryptographic-scale primes. For typical interview-sized n, trial division or sieve is sufficient.

Common Variations

Count primes less than n

(LeetCode #204) Apply the sieve, count True entries up to n. The sieve is faster than testing each number individually.

Find the nth prime

Sieve up to a generous upper bound (rough estimate: nth prime ≈ n × ln(n) for large n). Index into the list of primes.

Goldbach’s conjecture / sum of two primes

Unproven for all even n > 2, but verified up to extremely large values. For interview-sized inputs, sieve up to n then check pairs.

Prime factorization

Trial-divide by small primes from the sieve until n becomes 1 or until √n. Returns the multiset of prime factors.

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

Twin primes

Pairs (p, p+2) where both are prime. Found via sieve plus pairwise check.

Common Mistakes

• Forgetting to handle n < 2. 0 and 1 are not prime. Returning True for 1 is a common bug.
• Using i <= sqrt(n) with floats. Floating-point sqrt can have rounding issues at boundary values. Use i * i <= n with integer arithmetic, or int(n ** 0.5) + 1 with care.
• Sieve indexing errors. Off-by-one in the array size; should be n + 1 for indices 0..n. Forgetting to mark 0 and 1 as composite.
• Marking from 2i instead of i². Correct but does redundant work. The optimization to start at i² is standard.
• Using trial division when sieve is faster. If you need many primes up to N, sieve once. Calling is_prime in a loop is asymptotically slower.
• Forgetting Miller-Rabin’s probabilistic nature. With enough rounds (k = 20–40), the error probability is negligible, but it’s not zero. For cryptographic guarantees, use proven-deterministic variants (with specific witnesses for bounded n).

Frequently Asked Questions

See also: Compute x^y for Floats and Negative Exponents • Check if a Number Is a Power of Two • Two Sum: Find a Pair in an Array

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;

    // Eliminate multiples of 2 and 3
    if (n % 2 === 0 || n % 3 === 0) return false;

    // Check for factors of form 6k ± 1 up to √n
    // All primes > 3 are of form 6k ± 1
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) {
            return false;
        }
    }

    return true;
}

// Tests
console.log(isPrime(2));    // true
console.log(isPrime(17));   // true
console.log(isPrime(100));  // false
console.log(isPrime(97));   // true

function sieveOfEratosthenes(n) {
    if (n < 2) return [];

    // Initialize all as prime
    const isPrime = Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;

    // Sieve
    for (let p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            // Mark multiples of p as not prime
            // Start from p² (smaller multiples already marked)
            for (let multiple = p * p; multiple <= n; multiple += p) {
                isPrime[multiple] = false;
            }
        }
    }

    // Collect primes
    const primes = [];
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push(i);
        }
    }

    return primes;
}

// Test
console.log(sieveOfEratosthenes(30));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

console.log(sieveOfEratosthenes(100).length);  // 25 primes

function sieveOptimized(n) {
    if (n < 2) return [];
    if (n === 2) return [2];

    // Only store odd numbers
    const size = Math.floor((n - 1) / 2);
    const isPrime = Array(size + 1).fill(true);

    const primes = [2];  // 2 is the only even prime

    for (let i = 1; i <= size; i++) {
        if (isPrime[i]) {
            const p = 2 * i + 1;  // Convert index to actual number
            primes.push(p);

            // Mark multiples
            if (p * p <= n) {
                for (let j = (p * p - 1) / 2; j <= size; j += p) {
                    isPrime[j] = false;
                }
            }
        }
    }

    return primes;
}

console.log(sieveOptimized(30));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

function nthPrime(n) {
    if (n === 1) return 2;

    let count = 1;  // 2 is the first prime
    let candidate = 3;

    while (count < n) {
        if (isPrime(candidate)) {
            count++;
        }
        candidate += 2;  // Only check odd numbers
    }

    return candidate - 2;  // Back up to the nth prime
}

console.log(nthPrime(1));    // 2
console.log(nthPrime(10));   // 29
console.log(nthPrime(100));  // 541

function countPrimes(n) {
    if (n <= 2) return 0;

    const isPrime = Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let p = 2; p * p < n; p++) {
        if (isPrime[p]) {
            for (let multiple = p * p; multiple < n; multiple += p) {
                isPrime[multiple] = false;
            }
        }
    }

    // Count trues
    return isPrime.filter(x => x).length;
}

console.log(countPrimes(10));   // 4 (2, 3, 5, 7)
console.log(countPrimes(100));  // 25

Initial: [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]

p=2: Cross out 4,6,8,10,12,14,16,18,20,22,24,26,28,30
Remaining: [2,3,5,7,9,11,13,15,17,19,21,23,25,27,29]

p=3: Cross out 9,15,21,27 (multiples of 3, starting from 9=3²)
Remaining: [2,3,5,7,11,13,17,19,23,25,29]

p=5: Cross out 25 (5² = 25, only multiple ≤ 30)
Remaining: [2,3,5,7,11,13,17,19,23,29]

p=7: 7² = 49 > 30, stop

Primes: [2,3,5,7,11,13,17,19,23,29]

// Probabilistic primality test
// Correct for all primes, might incorrectly say composite is prime (rare)
function millerRabin(n, iterations = 5) {
    if (n < 2) return false;
    if (n === 2 || n === 3) return true;
    if (n % 2 === 0) return false;

    // Write n-1 as 2^r * d
    let d = n - 1;
    let r = 0;
    while (d % 2 === 0) {
        d /= 2;
        r++;
    }

    // Test with random witnesses
    for (let i = 0; i < iterations; i++) {
        const a = 2 + Math.floor(Math.random() * (n - 3));
        let x = modPow(a, d, n);

        if (x === 1 || x === n - 1) continue;

        let continueOuter = false;
        for (let j = 0; j < r - 1; j++) {
            x = (x * x) % n;
            if (x === n - 1) {
                continueOuter = true;
                break;
            }
        }

        if (!continueOuter) return false;
    }

    return true;
}

function modPow(base, exp, mod) {
    let result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 === 1) {
            result = (result * base) % mod;
        }
        exp = Math.floor(exp / 2);
        base = (base * base) % mod;
    }
    return result;
}

console.log(millerRabin(1000000007));  // true (large prime)