Sieve of Eratosthenes

@sieve_of_eratosthenes

The Sieve of Eratosthenes is an algorithm used to find all primes smaller than a given number (n). It works by iteratively marking the multiples of each prime number starting from 2.

Pseudo-code
function sieve_of_eratosthenes(n):
  # Step 1: Create a list that assumes all numbers are prime
  prime = array of size (n + 1), filled with True
  
  # 0 and 1 are not prime numbers
  prime[0] = False
  prime[1] = False
  
  # Step 2: Start checking from 2 up to sqrt(n)
  for p from 2 to sqrt(n):
    
    # If p is still marked as prime, it is a real prime
    if prime[p] == True:
      
      # Step 3: Mark all multiples of p as NOT prime
      # Start from p*p because smaller multiples were already handled
      for i from p*p to n step p:
        prime[i] = False
        
        # Think: we are crossing out multiples like a checklist
  
  # Step 4: Collect all numbers still marked True
  return all indices i where prime[i] == True
  • n n is the upper limit. Think of it like the last house on a street — you want to check every house number from 2 up to n to see which ones are 'special' (prime).
  • p p is the current number we are testing. If p is still marked as prime, we use it to eliminate its multiples. It is like a 'confirmed good number' that helps us cross out bad ones.
  • i i is used to walk through multiples of p. Imagine jumping in steps of size p (like p, 2p, 3p, 4p...) and marking those positions.
  • 2 2 is the first prime number and where everything starts. It is like the first 'trusted' number.
  • True True means 'this number is still considered prime'. If it becomes False, it means we discovered it is not prime.
Recipe Steps
1

Pick a number n. Imagine you want to find all prime numbers up to 20. So you are checking numbers from 2 to 20.

2

Write down all numbers from 2 to n. Think of it like a checklist where every number is 'possibly prime'.

3

Start with 2. Circle it because it is prime. Then cross out all multiples of 2 (4, 6, 8, 10...). Like removing all even numbers except 2.

4

Move to the next number that is not crossed out (which is 3). Circle it, then cross out its multiples (6, 9, 12...).

5

Keep repeating. Always pick the next uncrossed number and eliminate its multiples. It is like filtering out 'bad numbers' step by step.

6

Stop when you reach sqrt(n). After that, everything left uncrossed is prime.

Questions & Answers

Instead of checking each number individually, we remove all non-prime numbers by crossing out multiples of primes.

Because smaller multiples (like 2p, 3p) were already crossed out by smaller primes. This avoids repeating work.

Yes, because it was never crossed out.

It gets crossed out when processing 3, since 9 = 3 x 3.
- Big idea: We do not test if a number is prime directly. Instead, we eliminate all numbers that are definitely NOT prime.
- Analogy: Think of this like filtering bad apples from a basket. You remove the rotten ones (multiples), and what remains are good (prime).
- Optimization: Starting at p*p avoids repeating work and makes the algorithm faster.
- Efficiency: This algorithm is very fast for generating many primes at once (O(n log log n)).
- Common mistake: Forgetting to mark 0 and 1 as not prime.
- Tip: Visualizing this with a table and crossing numbers out helps a lot when learning.

Related Algorithms
Binary Search

Binary Search is a very fast algorithm used to find a value in a sorted list by repeatedly cutting the search space in half until the item is found or nothing is left.

View
Counting Sort

Counting Sort is a sorting algorithm that does not compare elements. Instead, it counts how many times each number appears and uses that information to place elements directly in their correct position.

View
Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from one starting node to all other nodes in a graph by always expanding the currently closest node first.

View