sieve of eratosthenes

Image of Author
March 22, 2025 (last updated July 25, 2025)

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

The sieve of Eratosthenes is an efficient technique for generating a list of primes.

Here is one way of thinking of it: First, imagine all the integers starting from 2 (up to some max number, if you like). Then, starting with 2, eliminate every multiple of it. Then do the same for 3. 4 has already been eliminated as a multiple of 2, so the next number to eliminate multiples of is 5, then 7, then 11, etc. Each new number you encounter must be a prime and each time you encounter a prime, you eliminate its multiples, ensuring that the next number will also be prime. By the end of the algorithm you are left with all the prime numbers from 2 to max.

Algorithmic optimizations

Use modular arithmetic to eliminate numbers from the sieve

It might be that the core loop of your implementation is taking the "next prime" and then eliminating its multiples. An efficient method for doing this is to iterate through the list and eliminate mod(n,p) = 0 (aka, retain non-zeros). The more naive implementation of calculating p*2 and seeing if it's still in the list, and then p*3, p*4, etc., will likely result in many misses for already eliminated numbers.

You can hard code the removal of the evens

It is memory and time efficient to construct a list of only the odd numbers and to start your primes list with [2]. This will look different across programming languages but it is likely more performant because the time it takes to filter out the evens will always be the longest in time and space.

You can start sieving after p^2

As you iterate through the sieve eliminating numbers you can always start eliminating at p^2 for a given prime p. This is because p^2 is p x p. The smaller multiple p x (p - 1) would have just been eliminated previously when sieving the (p - 1)'s. And the (p - 2)'s would have already eliminated the number p x (p - 2) before that, and so on all the way down to p x 2, which would have been eliminated in the 2-prime sieving.

You can stop sieving after reaching sqrt(n)

Factors come in pairs. The bigger the big the smaller the small. The biggest factor of 100 is 50 because the smallest factor is 2. If you want a larger and larger small factor, you need to lower and lower your big factor. The best you can get is sqrt(n) x sqrt(n). For example, 10 x 10 for 100.

By reductio ad absurdum, imagine a number larger than sqrt(n) that should be eliminated. It is not prime (because it should be eliminated by stipulation). So it must be composite. Let's call it c. What are c's prime factors, then? One must be less than sqrt(c) and the other larger than sqrt(c). But since c < n, then sqrt(c) < sqrt(n). This means the prime factor less than sqrt(c) would have been seen before passing sqrt(n) and therefore would have been eliminated already. So it must not have been eliminated (by stipulation) and also must have been eliminated (as a factor seen before reaching sqrt(n)).