DSA problem
Print All Primes up to N (Sieve of Eratosthenes)
Given an integer N, return every prime number from 2 to N using the Sieve of Eratosthenes.
Checking each number individually would cost about O(N * sqrt(N)). The sieve is far faster at O(N log log N). Create a boolean array of size N + 1 marked all true, then start at 2: it is prime, so mark every multiple of 2 as composite. Move to the next value still marked true (3), mark its multiples, and continue up to sqrt(N). Everything still marked true at the end is prime.
Starting each prime's crossing-out from i * i (rather than 2 * i) avoids redundant work, because smaller multiples were already handled by earlier primes. The sieve is a great lesson in pre-computation and eliminating candidates - ideas that reappear in caching and bloom filters.
Examples
N = 30[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]Constraints
- 2 <= N <= 10^7
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.