Sign in
Skip to solution
mediumDSA

How does the Sieve of Eratosthenes work?

76 views
01

Understand the problem

Explain the sieve.

mathsieve
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

To find all primes up to n, mark multiples of each prime starting from 2 as composite; unmarked numbers are prime. It runs in O(n log log n) — far faster than testing each number for primality individually.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Sieve of Eratosthenes
Run Playground
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):
                is_prime[multiple] = False
        p += 1
    return [i for i in range(2, n + 1) if is_prime[i]]


# --- demo ---
print(sieve(30))   # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 98 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track