Sieve of Eratosthenes
Efficiently find all prime numbers up to a specified limit.
Ready to start Sieve.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Instead of checking if each number is prime individually (Trial Division), we can iteratively mark the multiples of each prime number as composite. The numbers that remain unmarked are primes.
Concept
- Idea: Start with 2. Mark all multiples of 2 (4, 6, 8...) as composite. Move to the next unmarked number (3), mark its multiples. Continue until √N.
- Efficiency: Much faster than Trial Division for finding all primes up to N.
- Time Complexity: O(N log log N) - very close to linear!
How it Works
Algorithm:
- Create a list of booleans up to N, initialized to True.
- Set 0 and 1 to False.
- Loop
pfrom 2 to√N. - If
isPrime[p]is True:- Mark all multiples of
p(starting fromp*p) as False.
- Mark all multiples of
Step-by-Step Breakdown
Watch the visualization:
- Blue: Current prime number being processed.
- Red/X: Multiples being eliminated (marked as composite).
- Green: Numbers confirmed as prime.
When to Use
- Generating a list of all primes up to a large number (e.g., 10^7).
- Pre-computing primes for multiple queries.
When NOT to Use
- Checking primality for a single very large number (use Miller-Rabin).
- When memory is very limited (requires O(N) space).
How to Identify
"Find all primes up to N", "Sum of primes", "K-th prime number".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.