Understanding Sieve of Eratosthenes: Theory and Code

1. Introduction and Core Concepts

The sieve of eratosthenes is one of the oldest and most elegant algorithms in computer science and number theory, attributed to the ancient Greek mathematician Eratosthenes of Cyrene around 240 BCE. It is a highly efficient method for finding all prime numbers up to a given limit, and it remains a cornerstone of computational mathematics, cryptography, and algorithm education more than two millennia after its invention. Unlike trial division which tests each number individually for primality, the sieve of eratosthenes works by iteratively eliminating multiples of known primes, leaving only primes behind.

At its core, the sieve of eratosthenes is based on a simple observation: if a number is prime, then all of its multiples (except the number itself) must be composite. By systematically marking multiples starting from the smallest prime, 2, the algorithm filters out non-prime numbers in a sieve-like fashion. The name "sieve" is metaphorical — just as a physical sieve filters out fine particles while retaining larger ones, this algorithm filters out composite numbers to reveal primes. This elimination approach is dramatically faster than testing each number independently when you need to find many primes at once.

Understanding the sieve of eratosthenes matters for both theoretical and practical reasons. Theoretically, it introduces fundamental concepts like time-space tradeoffs, preprocessing versus query time, and the power of eliminating redundant work. Practically, generating primes efficiently is critical for modern computing tasks including cryptography, hashing, random number generation, and performance optimization. For students and professionals preparing for technical interviews, the sieve of eratosthenes is a frequently tested topic that demonstrates mastery of arrays, loops, optimization, and complexity analysis. Its simplicity makes it accessible to beginners, while its optimizations offer depth for advanced learners.

What Defines a Prime and Why Sieving Works

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, and 19. A composite number is any number greater than 1 that is not prime, meaning it can be expressed as a product of smaller primes. The fundamental theorem of arithmetic guarantees that every composite number has at least one prime factor less than or equal to its square root, which is the key insight that makes the sieve of eratosthenes efficient — we only need to sieve with primes up to sqrt(n) to find all primes up to n.

Prerequisites and Problem Statement

Given an integer n, the problem is to find all prime numbers p where 2 <= p <= n. The input is a single upper bound n, and the output is a list or set of primes in that range. The classic sieve of eratosthenes solves this in nearly linear time, which is a massive improvement over the naive approach of testing each number up to n with trial division. This batch-processing nature — finding all primes at once rather than answering individual primality queries — is what gives the sieve its advantage.

2. How It Works

The mechanism of the sieve of eratosthenes can be understood as a process of iterative elimination. You begin with a list of consecutive integers from 2 through n. Initially, all numbers are assumed to be prime. The algorithm then proceeds in rounds, each time taking the smallest unmarked number (which must be prime) and marking all of its multiples as composite. This process repeats until you have processed all numbers up to the square root of n, at which point all remaining unmarked numbers are guaranteed to be prime.

The reason we can stop at sqrt(n) is mathematically rigorous. If a composite number c <= n exists, it must have a divisor d <= sqrt(n). That divisor d is either prime itself or has a prime factor <= sqrt(n). Therefore, c would have already been marked as composite when we processed that prime factor. There is no need to continue sieving with primes larger than sqrt(n), because their multiples smaller than n would have already been marked by smaller prime factors. For example, to find primes up to 100, we only need to sieve with primes 2, 3, 5, and 7.

Another crucial optimization is where we start marking multiples. When sieving with prime p, we can start marking from p * p rather than 2 * p. All smaller multiples of p (like 2p, 3p, ..., (p-1)*p) would have already been marked when we processed smaller primes. For instance, when sieving with p=5, the multiples 10, 15, and 20 have already been marked by primes 2 and 3, so we can begin at 25. This seemingly small optimization significantly reduces redundant operations and is a standard part of any efficient implementation.

The Algorithm Step-by-Step

1. Create a boolean array is_prime[0..n] initialized to True, with is_prime[0] and is_prime[1] set to False.
2. Initialize p = 2, the smallest prime.
3. While p * p <= n: if is_prime[p] is True, then p is prime — iterate through multiples of p starting from p * p, marking each as not prime. Increment p to the next unmarked number.
4. After the loop completes, all indices i where is_prime[i] remains True correspond to prime numbers.

Visual Intuition

Imagine writing all numbers from 2 to 30 on a whiteboard. Circle 2 (prime) and cross out 4, 6, 8, 10, and so on. Move to the next uncrossed number, 3, circle it and cross out 9, 15, 21, 27 (6 and 12 are already crossed out). Next is 5, circle it and cross out 25. The next uncrossed number is 7, but 7*7=49 exceeds 30, so you stop. Every circled number and every remaining uncrossed number (11, 13, 17, 19, 23, 29) is prime. This physical process maps directly to the array-based implementation.

3. Implementation

Implementing the sieve of eratosthenes in Python is straightforward and serves as an excellent exercise in array manipulation and loop optimization. The classic implementation uses a boolean list to track primality and nested loops to mark multiples. Below are several implementations ranging from the clearest educational version to highly optimized variants used in competitive programming and production systems.

The basic implementation prioritizes readability and correctness. It directly translates the theoretical algorithm into code, making it ideal for learning and interviews where clarity is valued. Pay close attention to the range boundaries, the starting point of the inner loop, and the square root optimization — these details are where most bugs occur.

# Classic Sieve of Eratosthenes - Clear and Correct
def sieve_of_eratosthenes(n):
    """
    Return a list of all prime numbers up to n (inclusive)
    using the classic Sieve of Eratosthenes.
    """
    if n < 2:
        return []
    
    # Initialize boolean array: True means "potentially prime"
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    
    # Only need to sieve up to sqrt(n)
    p = 2
    while p * p <= n:
        if is_prime[p]:
            # Mark multiples of p starting from p*p
            # Smaller multiples already marked by smaller primes
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    
    # Collect all primes
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes

# Example usage
print(sieve_of_eratosthenes(30))
# Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

While the classic version is excellent for understanding, it can be optimized significantly. The most common optimization is to handle the even number 2 separately and then only sieve over odd numbers. This halves memory usage and reduces the number of marking operations by nearly 50%. Another micro-optimization is to use Python's slice assignment for faster marking, though the loop-based approach is more readable for interviews.

# Optimized Sieve - Skip Even Numbers (2x faster, 2x less memory)
def optimized_sieve(n):
    """
    Optimized sieve that only stores and sieves odd numbers.
    Handles 2 as a special case.
    """
    if n < 2:
        return []
    if n == 2:
        return [2]
    
    # Only track odd numbers: index i represents number 2*i + 3
    # Size needed for odd numbers from 3 to n
    size = (n - 1) // 2
    is_prime = [True] * size
    
    # Sieve only odd numbers
    # p corresponds to number 2*i + 3
    i = 0
    while (2 * i + 3) * (2 * i + 3) <= n:
        if is_prime[i]:
            p = 2 * i + 3
            # Start marking from p*p
            # p*p is odd, find its index: (p*p - 3) // 2
            start = (p * p - 3) // 2
            # Step by p (each step of p in number = step of p//2 in index for odd multiples,
            # but we need to step by p to stay on odd multiples)
            for j in range(start, size, p):
                is_prime[j] = False
        i += 1
    
    # Reconstruct primes: 2 plus all odd numbers still marked prime
    primes = [2] + [2 * i + 3 for i in range(size) if is_prime[i]]
    return primes

print(optimized_sieve(30))
# Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

For very large values of n (e.g., n > 10^8), even the optimized sieve may exceed memory limits. The segmented sieve solves this by processing the range in smaller chunks or segments that fit in cache, while still using the primes up to sqrt(n) generated by a classic sieve to mark composites in each segment. This is essential for competitive programming problems with large constraints.

# Segmented Sieve - For large n with limited memory
import math

def segmented_sieve(n):
    """
    Segmented Sieve of Eratosthenes for large n.
    Uses O(sqrt(n)) memory instead of O(n).
    """
    if n < 2:
        return []
    
    limit = int(math.isqrt(n)) + 1
    # Step 1: Find primes up to sqrt(n) using simple sieve
    base_primes = sieve_of_eratosthenes(limit)
    
    primes = base_primes.copy()
    
    # Step 2: Process segments
    segment_size = max(limit, 32768)  # Tune for cache efficiency
    low = limit + 1
    # Ensure low is odd
    if low % 2 == 0:
        low += 1
    
    while low <= n:
        high = min(low + segment_size - 1, n)
        # Create boolean array for current segment
        # Only store odd numbers in segment
        segment = [True] * ((high - low) // 2 + 1)
        
        for p in base_primes:
            if p == 2:
                continue  # Skip even prime, we only track odds
            # Find smallest multiple of p in [low, high]
            start = max(p * p, (low + p - 1) // p * p)
            # Make start odd if needed
            if start % 2 == 0:
                start += p
            # Mark multiples with step 2*p (to stay on odd multiples)
            for multiple in range(start, high + 1, 2 * p):
                segment[(multiple - low) // 2] = False
        
        # Collect primes from segment
        for i in range(len(segment)):
            if segment[i]:
                num = low + 2 * i
                if num <= n:
                    primes.append(num)
        
        low = high + 1
        if low % 2 == 0:
            low += 1
    
    return sorted(primes)

# Helper from earlier (needed for segmented sieve)
def sieve_of_eratosthenes(n):
    if n < 2:
        return []
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(math.isqrt(n)) + 1):
        if is_prime[p]:
            for m in range(p * p, n + 1, p):
                is_prime[m] = False
    return [i for i in range(2, n + 1) if is_prime[i]]

Beyond generating the list of primes, many applications require answering additional questions such as counting primes, finding the nth prime, or factorizing numbers. The sieve can be extended to store the smallest prime factor (SPF) for each number, enabling O(log n) factorization of any number up to n after O(n log log n) preprocessing.

# Sieve with Smallest Prime Factor (SPF) - Enables fast factorization
def sieve_with_spf(n):
    """
    Build SPF array where spf[x] = smallest prime factor of x.
    Allows O(log n) factorization of any number <= n.
    """
    if n < 2:
        return [], []
    
    spf = list(range(n + 1))  # spf[i] initially i
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                if is_prime[multiple]:
                    # First time we mark it, p is its smallest prime factor
                    spf[multiple] = p
                is_prime[multiple] = False
    
    primes = [i for i in range(2, n + 1) if is_prime[i]]
    return primes, spf

def factorize(x, spf):
    """Factorize x using precomputed spf array in O(log x) time."""
    factors = []
    while x > 1:
        p = spf[x]
        factors.append(p)
        x //= p
    return factors

primes, spf = sieve_with_spf(30)
print(f"Primes: {primes}")
print(f"Factorization of 84: {factorize(84, spf)}")  # [2, 2, 3, 7]
print(f"Factorization of 97: {factorize(97, spf)}")  # [97] (prime)

4. Step-by-Step Example

To solidify understanding, let us walk through the sieve of eratosthenes concretely for n = 30. This example is large enough to demonstrate all key behaviors — including the sqrt(n) stopping condition and the p*p starting point — while remaining small enough to follow manually. We will track the boolean array state after each prime is processed.

We begin with numbers 2 through 30, all initially considered prime candidates. We create an array is_prime[0..30] where indices 0 and 1 are immediately marked False. The remaining indices 2-30 are True. The square root of 30 is approximately 5.47, so we will only need to sieve with primes p where p <= 5, namely 2, 3, and 5. This is a critical point: even though 7, 11, and others are prime, we do not need to use them as sieving bases.

Processing p = 2: Since is_prime[2] is True, we mark multiples of 2 starting from 2*2 = 4. We mark 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 as composite (False). After this step, half the numbers are eliminated. The next unmarked number after 2 is 3.

Processing p = 3: is_prime[3] is still True, so 3 is prime. We mark multiples of 3 starting from 3*3 = 9. We mark 9, 15, 21, 27. Note that 6, 12, 18, 24, 30 were already marked by p=2, so starting at 9 avoids redundant work. The next unmarked number after 3 is 5 (since 4 is marked).

Processing p = 5: is_prime[5] is True, so 5 is prime. We mark multiples starting from 5*5 = 25. We mark 25 only (30 is already marked, and the next multiple 35 exceeds 30). The next candidate would be 7, but 7*7 = 49 > 30, so we stop sieving. All numbers that remain marked True are primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Notice that 7 was never used as a sieving prime, yet it correctly remains marked as prime.

State Table Walkthrough

The following table shows the state after each sieving step. "T" means still considered prime, "F" means marked composite. Bold indicates the prime just used for sieving.

Why Starting at p*p Matters

In our example, when p=5, starting at 10 would have redundantly remarked 10, 15, and 20. Starting at 25 does only the necessary work. For larger n, this optimization becomes increasingly valuable. When p is large, say p=101, starting at 202 versus 10201 saves marking 100 multiples that were already handled. This is why the inner loop is for multiple in range(p * p, n + 1, p) and not range(2 * p, n + 1, p).

5. Complexity Analysis

The complexity analysis of the sieve of eratosthenes is a classic topic that reveals why it is so efficient. Unlike naive primality testing, its time complexity is not immediately obvious and requires understanding of harmonic series and prime number distribution. The analysis also highlights the tradeoff between time efficiency and memory consumption that characterizes many preprocessing algorithms.

The time complexity is often stated as O(n log log n), which is nearly linear. This result comes from the sum over all primes p <= n of n/p, which approximates n * (log log n) by Mertens' theorem. More precisely, the number of marking operations is n/2 + n/3 + n/5 + n/7 + ... for primes up to sqrt(n), but bounded by the sum over all primes up to n. The harmonic series over primes grows as log log n, giving the famous bound. For practical purposes, log log n grows extremely slowly — for n = 10^9, log log n is only about 3 — so the sieve behaves almost linearly.

Space complexity is O(n) for the classic implementation, as we store a boolean array of size n+1. Each entry is typically a Python bool or byte. Optimized variants reduce this to O(n/2) by storing only odd numbers, or O(sqrt(n)) for the segmented sieve. The SPF variant also uses O(n) for the additional integer array. In environments with strict memory limits, the segmented sieve is preferred despite its slightly higher constant factor in time.

Understanding the log log n Factor

The log log n factor is one of the slowest growing functions in computer science. To appreciate its efficiency, compare n log log n to n log n (typical sorting complexity). For n = 1,000,000, n log n is about 20,000,000 operations while n log log n is about 2,600,000 — nearly an order of magnitude difference. This near-linear performance is why the sieve of eratosthenes can generate primes up to 10^7 or 10^8 in seconds in Python, and up to 10^9 in optimized languages like C++.

Cache and Constant Factors

While Big O notation captures asymptotic growth, constant factors and cache behavior matter in practice. The classic sieve has excellent cache locality when n fits in L3 cache, but performance degrades when the boolean array exceeds cache size due to random-access marking patterns. The segmented sieve explicitly addresses this by working on cache-sized segments, often outperforming the classic sieve for large n despite identical Big O complexity. In Python, using a bytearray or array('b') instead of a list of booleans can also improve cache efficiency and reduce memory overhead.

6. Variations and Optimizations

The classic sieve of eratosthenes is already efficient, but numerous variations and optimizations exist that improve performance, reduce memory, or adapt the algorithm to special constraints. Understanding these variants is valuable for competitive programming, system design, and interviews where follow-up optimization questions are common.

The wheel factorization optimization generalizes the odd-only idea. A wheel of size 30, for example, skips all multiples of 2, 3, and 5, storing only numbers coprime to 30 (i.e., numbers congruent to 1, 7, 11, 13, 17, 19, 23, 29 mod 30). This reduces the array size to about 26.7% of the original (8/30) and eliminates marking operations for those small primes entirely. Wheels of size 210 (2*3*5*7) and 2310 (2*3*5*7*11) offer further reductions but with diminishing returns and increased code complexity.

The Sieve of Sundaram is an alternative that eliminates numbers of the form i + j + 2ij where 1 <= i <= j and i + j + 2ij <= n, then maps remaining numbers to primes via 2x+1. It is slightly less efficient than the optimized Eratosthenes but is historically interesting and sometimes appears in academic contexts. The Sieve of Atkin uses quadratic forms and modular arithmetic to mark primes in O(n) time theoretically, but its higher constant factors and complex implementation mean it rarely outperforms a well-optimized Eratosthenes in practice for n < 10^10.

For extremely large ranges where n exceeds available memory, the segmented sieve is the standard solution. It can generate primes up to 10^12 by only requiring O(sqrt(n)) memory for base primes plus the segment size. Another variant, the incremental or dynamic sieve, generates primes on-demand without a fixed upper bound, using a dictionary to track the next multiple of each prime — useful for streaming applications or when n is not known in advance.

Bitset and Bytearray Optimization

In Python and other languages, replacing a list of booleans with a bytearray or bitset can reduce memory by 4-8x and improve speed due to better cache utilization. Python's bytearray stores each entry as a single byte, while a bitset packs 8 booleans per byte. Libraries like numpy or the builtin array module can provide further speedups through vectorized operations, though they add dependencies.

Linear Sieve (Euler Sieve)

The linear sieve, also called Euler's sieve, achieves O(n) time by ensuring each composite is marked exactly once by its smallest prime factor. It maintains a list of primes found so far and for each number i, iterates over primes p where p <= spf[i] and marks i*p as composite. While asymptotically faster than O(n log log n), its constant factors are higher and it is more complex to implement, so it is primarily used when the SPF array is needed for factorization.

7. Real-World Applications

Although the sieve of eratosthenes may seem like a purely academic exercise, its ability to generate primes efficiently underpins numerous real-world systems. Any application that requires many primes, fast factorization, or prime counting benefits from sieving as a preprocessing step. The key advantage is amortization: paying O(n log log n) once to answer many subsequent queries in O(1) or O(log n) time.

In cryptography, the sieve is used to generate prime tables for key generation, primality testing, and parameter selection. While RSA key generation requires large random primes (1024+ bits) that are too large for sieving directly, sieving is used to quickly eliminate candidates with small prime factors before applying expensive probabilistic tests like Miller-Rabin. This trial division by small primes using a pre-sieved table dramatically speeds up the search for large primes. Similarly, Diffie-Hellman and elliptic curve cryptography use sieved primes for safe prime generation and curve parameter validation.

In software engineering and systems design, prime numbers generated by sieving are used for hash table sizing, where table capacities chosen as primes reduce collisions for certain hash functions. Database systems and language runtimes (like Python's dict and Java's HashMap) historically used prime-sized tables. Sieving also supports efficient implementation of Bloom filters, consistent hashing, and pseudo-random number generators that rely on prime moduli. In web servers and networking, primes are used for load balancing algorithms, sharding strategies, and generating unique identifiers with low collision rates.

Beyond computing infrastructure, the sieve appears in mathematical research, competitive programming, and education. Prime counting functions, Goldbach conjecture verification, and prime gap studies all rely on efficient sieving to generate data up to large bounds. In data science, sieving can optimize algorithms that require coprime sampling or periodic scheduling with minimal overlap.

Performance in Production Systems

In production, sieving is typically done once at startup or as a batch job, with results cached in memory or on disk. For example, a web service that needs to quickly find the next prime for hash table resizing might precompute primes up to 10 million at deploy time and serve queries from the cached list. This pattern — expensive preprocessing for cheap queries — is a common system design tradeoff, and the sieve of eratosthenes is a textbook example of when it pays off.

8. Comparison with Alternatives

Choosing the right prime-generation method depends on the problem constraints: whether you need all primes up to n or just to test a single number, the size of n, memory limits, and whether queries are offline or online. The sieve of eratosthenes excels at batch generation but is not always the best tool for every primality-related task.

Trial division is the simplest alternative: to test if x is prime, try dividing by all integers up to sqrt(x), or just primes up to sqrt(x). It uses O(1) memory and is optimal for testing a single number or a few numbers, especially when n is large and x is isolated. However, to find all primes up to n, trial division requires O(n sqrt(n)) time, which is prohibitively slow for n > 10^5. Probabilistic tests like Miller-Rabin and deterministic tests like AKS are designed for testing very large numbers (hundreds of digits) where sieving is impossible due to memory constraints.

Among sieves, the Sieve of Sundaram and Sieve of Atkin are often compared to Eratosthenes. Sundaram is conceptually similar but slightly slower in practice due to extra arithmetic. Atkin has better theoretical complexity O(n) but is more complex and has higher constant factors, making it slower for n < 10^9 in most implementations. The segmented and linear sieves are not competitors but optimizations of Eratosthenes for specific constraints — memory-limited and SPF-generation scenarios respectively.

When to Choose What

Use the classic or optimized sieve of eratosthenes when you need all primes up to n and n fits in memory — this covers the vast majority of interview and competitive programming problems. Use trial division when you only need to test one or a few numbers for primality, especially if those numbers are large and sparse. Use the segmented sieve when n is huge (10^9+) or memory is constrained, such as on embedded systems. Use Miller-Rabin when numbers exceed 64-bit and you need probabilistic primality testing for cryptography. Understanding these tradeoffs demonstrates mature algorithmic judgment beyond merely knowing one algorithm.

9. Common Mistakes and Best Practices

Despite its conceptual simplicity, the sieve of eratosthenes is surprisingly easy to implement incorrectly, especially under interview pressure or when optimizing. Recognizing common pitfalls and following best practices ensures correctness, efficiency, and maintainability.

A frequent mistake is starting the inner marking loop from 2*p instead of p*p. While this still produces correct results, it does redundant work and can double execution time for large n. Another common error is incorrect loop bounds: iterating p up to n instead of sqrt(n) wastes time, while iterating only up to n/2 misses the optimization entirely. Off-by-one errors in array sizing (n vs n+1) and range endpoints (n+1 vs n) frequently cause IndexError or missing the prime n itself when n is prime.

Memory-related mistakes include using a Python list of ints (28 bytes each) instead of booleans or bytearray, causing memory blowup for large n. Forgetting to handle edge cases n < 2 (where no primes exist) leads to crashes or incorrect outputs. In Python specifically, using a naive for loop with Python-level operations for marking can be 10x slower than using slice assignment or numpy, though readability should be prioritized in interviews.

Best practices include: always handle n < 2 as a guard clause; use math.isqrt(n) for accurate integer square root instead of int(n**0.5) which can have floating point errors for large n; start marking from p*p; iterate p only up to sqrt(n); use a bytearray for memory efficiency in production; and write helper functions to separate sieving from prime collection for testability. When code will be reused, encapsulate the sieve in a class that caches results and supports queries like is_prime(x), count_primes(), and nth_prime(k).

Checklist for Correct Implementation

• Array size is n+1 to include index n
• is_prime[0] and is_prime[1] are False
• Outer loop condition is p * p <= n or p <= isqrt(n)
• Inner loop starts at p * p, steps by p
• Edge case n < 2 returns empty list
• Result collection iterates from 2 to n inclusive
• Use <= not < when comparing p*p to n

Testing and Validation

Always test with small known cases: n=2 should return [2], n=10 should return [2,3,5,7], n=30 should return 10 primes, and n=100 should return 25 primes. Verify that the count matches known prime-counting function values π(n). For larger n, cross-check against a known prime list or use a simple trial division verifier for a sample of results. Performance testing with n=10^6 should complete well under one second in Python for an optimized implementation.

10. Interview Questions

The sieve of eratosthenes is a staple of technical interviews because it tests array manipulation, loop reasoning, complexity analysis, and optimization skills in a compact problem. Interviewers often start with the basic sieve and then add follow-up constraints to probe deeper understanding. Below are common questions with strategic approaches to answering them.

Question 1: Implement the Sieve and Count Primes

"Write a function countPrimes(n) that returns the number of primes less than n. n can be up to 5*10^6. Optimize for speed." This is LeetCode 204. The expected solution is the classic sieve with the p*p and sqrt(n) optimizations. Mention that you would use a bytearray for speed and that counting can be done by summing the boolean array. Discuss the O(n log log n) time and O(n) space tradeoff. A strong candidate will also mention that for multiple queries, you would precompute once and answer each query in O(1).

Question 2: Segmented Sieve for Large n

"How would you find all primes between 10^9 and 10^9 + 10^5 when you cannot allocate an array of size 10^9?" This tests whether you know the segmented sieve. Explain that you first sieve up to sqrt(10^9 + 10^5) ≈ 31623 to get base primes, then use those primes to mark composites in the target segment. Emphasize the O(sqrt(n)) memory benefit and that the segment size can be tuned to fit in cache. This question distinguishes candidates who have memorized the basic sieve from those who understand its memory limitations.

Question 3: Prime Factorization with Sieve

"Given up to 10^5 queries, each asking to factorize a number up to 10^6, how would you answer efficiently?" The naive approach of trial division per query is too slow. The optimal solution is to precompute the smallest prime factor (SPF) array using a modified sieve in O(n log log n), then answer each factorization query in O(log n) by repeatedly dividing by spf[x]. This demonstrates understanding of preprocessing and the versatility of sieving beyond just listing primes. Be prepared to code both the SPF sieve and the factorization function.

Question 4: Optimizing the Sieve — Why Start at p*p?

"In your sieve implementation, why do you start marking multiples from p*p instead of 2*p? What is the complexity impact?" This is a conceptual follow-up that tests mathematical reasoning. Explain that any multiple k*p where k < p would have already been marked when processing the prime factor of k (which is < p). Therefore starting at p*p avoids redundant marking. While the Big O remains O(n log log n), the constant factor improves significantly — roughly 30-40% fewer marking operations for large n — and shows attention to detail.

Question 5: Sieve vs Trial Division — When to Use Which?

"You need to determine if a single 12-digit number is prime. Would you use the sieve of eratosthenes?" The answer is no. For a single number, trial division up to sqrt(n) or Miller-Rabin is more appropriate because sieving up to 10^12 would require terabytes of memory. The sieve is optimal when you need many primes or many queries amortized over the same range. This question evaluates system design judgment and the ability to choose the right tool for the problem constraints, not just implement an algorithm.

Preparing for these questions involves not only coding the sieve fluently but also articulating the tradeoffs, optimizations, and extensions. Practice implementing the sieve from memory, analyzing its complexity without hesitation, and discussing at least one optimization (odd-only or segmented) to demonstrate depth. Interviewers value candidates who can reason about when not to use the sieve as much as those who can code it.