Sieve of Eratosthenes

Generate all prime numbers up to a given limit using the classic sieve algorithm.

primes sieve loops boolean-array

Implement the function `eratosthenes(n)` that returns a list of all prime numbers <= n in ascending order. The function must use the Sieve of Eratosthenes algorithm.

- If n < 2, return an empty list.
- The result must be a list of integers in ascending order.
- The function should handle n=0 and n=1 gracefully.
- You must mark multiples of each prime starting from 2.

**Signature:** `def eratosthenes(n: int) -> list[int]:`

Constraints

- 0 <= n <= 10^6

Example

>>> eratosthenes(10)
[2, 3, 5, 7]
>>> eratosthenes(2)
[2]
>>> eratosthenes(0)
[]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Create a boolean list of size n+1, initially all True (assuming prime). Set 0 and 1 to False.

Loop from 2 to sqrt(n). For each prime i, mark all multiples i*j (j>=i, i*j<=n) as False.

Finally, collect indices that are still True.

For n<2, return an empty list immediately.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.