The Sieve of Eratosthenes

Prime numbers are the building blocks of number theory, yet finding them efficiently has challenged mathematicians for millennia. Among the earliest and most elegant solutions is the Sieve of Eratosthenes—an algorithm devised over 2,000 years ago by the Greek mathematician Eratosthenes of Cyrene.

Despite its ancient origins, this method remains relevant today due to its simplicity and efficiency in generating all prime numbers up to a given limit.

Understanding the Sieve Idea

consider we have a list of numbers, then we want to eliminate the ones which are which are not primes (i.e multiple of primes), this way whatever is left is prime.

for better understanding we won’t be including 2 in our starting list so that we can generate prime numbers greater than it. So we are left with odd numbers which can be represented as a function of their position as F(i)=2i+3 and the index of a number of value v vice-versa will be G(v)=v−3/2​ (this mapping will later allow us to translate better the sieve array).

The next question is, how do we start marking the multiples for a given prime p ?

we need to find the step size between the multiples of given prime in our list of (2i + 3). since we are only using odd numbers the consecutive multiples for a prime (2i+3) will be k(2i+3) and (k + 2)(2i + 3) where k > i. (since we are using odd only so after k we go for k + 2 rather than k + 1)

step size between k(2i+3) and (k + 2)(2i + 3) can be found from the index to value relation we got earlier

step(i) = G((k+2)(2i + 3)) - G(k(2i + 3))

\= G(2ki + 3k + 4i+ 6) - G(2ki + 3k)

\= ((2ki + 3k + 4i + 6) - 3) / 2 - ((2ki + 3k) - 3) / 2

\= (4i + 6) / 2 = 2i + 3

Now say we try to mark out the non primes between 3 to 49. This is what the sive will look when we do the first iteration of marking.
3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49

before we start the marking for the next prime we can see the multiples of it less than p² are already marked out, in our case for 5 the value 15 is already marked. We can use this as an optimisation so that we start marking the multiples only after the value of p². For that we need a index to value relation for p² which we can easily find using our earlier function.

G(p²) = (2i + 3)² - 3 / 2 = 2i² + 6i + 3

Now, let’s put att this to code

function sievePrimes(n: number): number[] {
  if (n < 2) return [];

  // Only odd numbers from 3 to n
  const sieveSize = Math.floor((n - 1) / 2);
  const isPrime = new Array(sieveSize).fill(true);
  const sqrtN = Math.floor(Math.sqrt(n));
  const getPrimeSquaredIndex = (i: number) => 2 * i * (i + 3) + 3;

  for (let i = 0; 2 * i + 3 <= sqrtN; i++) {
    // step size between multiples 2*i + 3
    if (isPrime[i]) {
      const p = 2 * i + 3;
      let start = (p * p - 3) / 2;
      // Mark multiples of p starting from p²
      for (let j = start; j < sieveSize; j += p) {
        isPrime[j] = false;
      }
    }
  }

  for (let i = 0; i < sieveSize; i++) {
    if (isPrime[i]) primes.push(2 * i + 3);
  }

  return primes;
}

Why we did iteration only till <= sqrtN ?

this is something which took me time to understand and i’m sure you are also wondering about the same.

This is an important optimization in the sieve method. To mark all composite numbers ≤ N, we only need to mark multiples of primes ≤ √N. If a number >N​ is composite, it must have a prime factor ≤ √N, so it will already be marked when we process smaller primes. This is because composite numbers have factors always ≤ √N.

for e.g

Let N=36. √N = 6,
Possible factor pairs:

• 2×18 → 2≤6

• 3×12 → 3≤6

• 4×9→ 4≤6

• 6×6→ 6≤6

thus to mark N we don’t need to iterate till N, √N will suffice just fine.

🔑 Summary

This ancient algorithm finds all primes up to N by eliminating multiples of each prime starting from 2. The optimized version skips even numbers, cutting work in half.

Key steps:

1. Start at p² (smaller multiples are already marked).

2. Only check primes ≤ √N (any larger factor would've been caught earlier).

3. we used mathematical interpolation to arrive at our optimizations

Eratosthenes developed the sieve algorithm around 3rd Century BC which was more than 2000 years ago around that time algebra was not even formulated properly.

📚 Further Reading

• From Mathematics to Generic Programming by Alexander A. Stepanov and Daniel E. Rose

💬 Suggestions

If you’ve made it this far, thank you! I’d love to hear your thoughts on the article. If you have suggestions, corrections, or just want to chat — feel free to reach out via mail or linkedin or leave a comment.