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 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 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 Used to walk through multiples of p. Imagine jumping in steps of size p (like p, 2p, 3p, 4p...) and marking those positions.
  • 2 First prime number and where everything starts. It is like the first 'trusted' number.
  • 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.
- We do not test if a number is prime directly. Instead, we eliminate all numbers that are definitely NOT prime.
- Think of this like filtering bad apples from a basket. You remove the rotten ones (multiples), and what remains are good (prime).
- Starting at p*p avoids repeating work and makes the algorithm faster.
- This algorithm is very fast for generating many primes at once (O(n log log n)).
- Visualizing this with a table and crossing numbers out helps a lot when learning.

Related Algorithms
Backtracking

Backtracking is a problem-solving technique used in algorithms to find a solution by exploring all possible solutions and retracting when a dead end is reached. It's often used for solving puzzles, finding paths, or scheduling tasks.

View
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
Boyer–Moore string-search algorithm

The Boyer–Moore string-search algorithm is a fast string searching algorithm that is often used in text editors and compilers. It does this by trying to match the pattern from the end of the string, making it efficient for large strings. It's used when you need to find a substring within a large text or string.

View