Sieve of Eratosthenes Algorithm

When it comes to efficiently finding all prime numbers less than a given limit 𝑁, the Sieve of Eratosthenes stands out as one of the most elegant and efficient algorithms.

Developed by the ancient Greek mathematician Eratosthenes, this algorithm systematically eliminates non-prime numbers, significantly reducing computation time compared to naive methods. In this article, we'll explore how the Sieve of Eratosthenes works, analyze its time complexity, and implement it in code.

Let's dive in! 🚀

Understanding the Concept

To find all prime numbers less than 𝑁 using the Sieve of Eratosthenes, follow these steps:

1. List all numbers from 0 to 𝑁-1.

2. Assume all numbers are prime initially (except 0 and 1, which are not primes).

3. Start at 2, the smallest prime number.

4. Mark all multiples of 2 as non-prime (false), except 2 itself.

5. Move to the next number that is true and mark all its multiples, except itself as non-prime.

6. Repeat this process until you reach √N or sqrt(N).

Why stop at 𝑁?

If we are finding primes less than 100, we stop at 10 because √100 = 10 . Any composite number greater than 𝑁 must have a factor already marked earlier in the process. The numbers that remain unmarked are all prime.

Visualizing the Algorithm

1. We start by marking 0 and 1 as not prime

2. Mark 2 as prime while all its multiples as not prime

3. Go to the next unvisited tile, which is 3

4. Mark it as prime and its multiples as not prime

5. Go to the next unvisited tile, but it is greater than the square root of 24, so we stop

6. Mark all the unvisited tiles as prime

The Pseudocode

Find all primes less than N

if N <= 2:
    return an empty list

create a list is_prime of size N, initialized to true
set is_prime[0] and is_prime[1] to false (since 0 and 1 are not prime)

for i from 2 to √N+1:
    if is_prime[i] is true:
        for x from i² to N, incrementing by i:
            set is_prime[x] to false

return all indices where is_prime[index] is true

Implementing the Algorithm

from math import isqrt

def primes_less_than(N: int) -> list[int]:
    if N <= 2:
        return []

    is_prime = [True] * N
    is_prime[0] = False
    is_prime[1] = False

    for i in range(2, isqrt(N)+1):
        if is_prime[i]:
            for x in range(i*i, N, i):
                is_prime[x] = False

    return [i for i in range(N) if is_prime[i]]

If you found this article helpful, feel free to share your thoughts or experiment with optimizations to make it even faster. Happy coding! 🚀