Algorithm1 Practice1 Interview

Sieve of Eratosthenes

GuideCode Labs

Mark multiples of discovered primes to enumerate primes up to a fixed bound efficiently. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Sieve of Eratosthenes when the prompt's constraints and required operations match this shape: Mark multiples of discovered primes to enumerate primes up to a fixed bound efficiently.

On this page · Mark Multiples from Each Prime

Checking your account…

Mark Multiples from Each Prime

The sieve stores primality for every integer through a limit. When an unmarked base is reached, it is prime and its composite multiples can be crossed off.

Start Crossing Off at Prime Squared

Multiples below p squared already have a smaller prime factor and were marked earlier. Starting at p squared avoids redundant work without missing composites.

Trace Sieve Marking

Reference

def sieve_trace(limit):
    is_prime=[True]*(limit+1)
    if limit>=0:is_prime[0]=False
    if limit>=1:is_prime[1]=False
    trace=[];prime=2
    while prime*prime<=limit:
        if is_prime[prime]:
            marked=[]
            for multiple in range(prime*prime,limit+1,prime):
                if is_prime[multiple]:marked.append(multiple)
                is_prime[multiple]=False
            trace.append([prime,marked])
        prime+=1
    return trace

Practice

Implement sieve_trace(limit). Return [prime,marked_multiples] for each base prime through sqrt(limit).

def sieve_trace(limit):
    pass

Public tests

Begin marking at prime squared

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Stop Base Primes at the Square Root

Every composite n has a factor no greater than square root n. Once p squared exceeds the limit, every remaining unmarked number is prime.

List Primes through a Limit

Reference

def primes_through(limit):
    if limit<2:return []
    is_prime=[True]*(limit+1);is_prime[0]=is_prime[1]=False
    prime=2
    while prime*prime<=limit:
        if is_prime[prime]:
            for multiple in range(prime*prime,limit+1,prime):is_prime[multiple]=False
        prime+=1
    return [value for value in range(2,limit+1) if is_prime[value]]

Practice

Implement primes_through(limit). Return every prime less than or equal to limit.

def primes_through(limit):
    pass

Public tests

Keep unmarked values at least two

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose a Full or Segmented Sieve

Use a full sieve for repeated prime queries through a manageable limit at O(n log log n) time and O(n) space. Use a segmented sieve for a large interval when storing every earlier Boolean is impractical.

Explain It in an Interview

Say: “An unmarked p is prime; I start at p squared because smaller multiples already have smaller factors. Base primes stop at the square root.” Handle zero, one, inclusive limit, and memory explicitly.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Sieve of Eratosthenes proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Sieve of Eratosthenes complete workflow	`O(n log log n)`	`O(n log log n)`	Mark all candidates, cross out multiples from p squared for each remaining prime p, then collect marked values.

Space

O(n) for the focused Generate Primes with a Sieve implementation.

Assumptions

Every composite has a prime factor no greater than its square root and is crossed out. No prime is a multiple of a smaller prime, so marked values are exactly the primes.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Sieve of Eratosthenes invariant before coding and preserve it after every update, traversal step, or recursive return.
The transformed state is equivalent to the original query under the documented number rule.
Each update strictly reduces the remaining range or unresolved magnitude.
Represent primality for every candidate. Preserve this claim after every transition.
Start crossing out at p*p and stop sieving after sqrt(limit). Preserve this claim after every transition.

When To Use Or Avoid Sieve of Eratosthenes

Use It When

Use Sieve of Eratosthenes when this precondition is stated or can be proved: The integer domain and divisibility, primality, or congruence contract are explicit.
Use it when this maintained state removes repeated work: The transformed state is equivalent to the original query under the documented number rule.

Choose Another Tool When

Avoid Sieve of Eratosthenes when this precondition is absent: The integer domain and divisibility, primality, or congruence contract are explicit.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The integer domain and divisibility, primality, or congruence contract are explicit.

Avoid

def primes_up_to(limit):
    pass

Use instead

def primes_up_to(limit):
    if limit < 2:
        return []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    candidate = 2
    while candidate * candidate <= limit:
        if is_prime[candidate]:
            for multiple in range(candidate * candidate, limit + 1, candidate):
                is_prime[multiple] = False
        candidate += 1
    return [value for value in range(2, limit + 1) if is_prime[value]]

Where you will hit this: Generate Primes with a Sieve(opens in a new tab)

Breaking the state transition

Treats every value at least two as prime.

Prevent it: Preserve this proof obligation: Each transformation preserves the required number-theoretic relation while moving toward a terminal bound.

Avoid

def primes_up_to(limit):
    return list(range(2,limit+1))

Use instead

def primes_up_to(limit):
    if limit < 2:
        return []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    candidate = 2
    while candidate * candidate <= limit:
        if is_prime[candidate]:
            for multiple in range(candidate * candidate, limit + 1, candidate):
                is_prime[multiple] = False
        candidate += 1
    return [value for value in range(2, limit + 1) if is_prime[value]]

Where you will hit this: Generate Primes with a Sieve(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n log log n).

Avoid

def primes_up_to(limit):
    return list(range(2,limit+1))

Use instead

def primes_up_to(limit):
    if limit < 2:
        return []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    candidate = 2
    while candidate * candidate <= limit:
        if is_prime[candidate]:
            for multiple in range(candidate * candidate, limit + 1, candidate):
                is_prime[multiple] = False
        candidate += 1
    return [value for value in range(2, limit + 1) if is_prime[value]]

Where you will hit this: Count Subsequences by Minimum and Maximum(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…