54. Sieve of Eratosthenes

Medium

Topics

Helpful tools to learn & understand

Watch key transitions, pointers, and variables update step-by-step.

Open

Read clean, documented implementations across multiple patterns.

View Code

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Input: n = 10

Output: [2, 3, 5, 7]

Explanation: The prime numbers less than or equal to 10 are 2, 3, 5, and 7.

Input: n = 20

Output: [2, 3, 5, 7, 11, 13, 17, 19]

Explanation: The prime numbers less than or equal to 20 are 2, 3, 5, 7, 11, 13, 17, and 19.

Input: n = 2

Output: [2]

Explanation: The only prime number less than or equal to 2 is 2.

Input: n = 1

Output: []

Explanation: There are no prime numbers less than or equal to 1.

Time Complexity

O(n log log n)

Space Complexity

O(n)