mediumDSA

How does the Sieve of Eratosthenes work?

Q: How does the Sieve of Eratosthenes work?

**Intuition.** To find every prime up to n , don't test each number for primality. Instead, start at 2 and **cross out all its multiples**, then the next uncrossed number (3), cross out its multiples, and so on. Whatever survives unmarked is prime. cross multiples of 2 (red), then 3 (amber); primes stay green 2 <rect x="68" y="34" width="44" height="34" rx="5" fill="#22c55e" fill-o

76 views

Understand the problem

Explain the sieve.

mathsieve

Attempt it yourself

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

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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]

Join the discussion

Discussion (0)

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

How do you check if an array can be partitioned into two equal-sum subsets?

What is topological sort and when is it used?