Prime Sieve Introduction

The Question

For this article we are interested in the following question, does there exist a method to effectively compute prime numbers?

Naive Method

We know we can check if a number is prime by checking all the numbers smaller than it. If not a single number can divide the number then the number is prime. This method results in O(n^2) time complexity where n is the highest prime number we want to compute.

Improvements

We can improve this by realizing that we only need to check up to the square root of a number. Any divisors that are greater than the square root of a number will have a matching divisor less than the square root of the number. Mathematically speaking, let us define n as an arbitrary composite number and d as a divisor of the number that is greater than its square root. We know for a fact that if d is a divisor greater than the square root then n/d is also a divisor of n but n/d must be less than the square root. Therefore, we only need to check if n/d is a divisor of n and if it is then n is composite. This property holds true for any d greater than the square root so therefore we only need to check up to sqrt(n). Take for example the number 16, we know 16 = 2 * 8 so we realize that for the number 16 there exists a divisor smaller than the square root (4) that matches 8 which is 2. This means compared to before, our new time complexity is O(n*sqrt(n)), but can we do even better?

Sieve of Erastothenes

Formally speaking, the technique we are about to introduce is called the sieve of Eratosthenes but for simplicity we will refer to it as sieve or prime sieve. This technique has a very simple idea, suppose we want to compute all prime numbers less than or equal to some number n. We start by looping from 1 to n, if we encounter a prime number we mark all the multiples of the prime number as not prime. Our new time complexity then becomes O(n + n/2 + n/3 + n/5 + n/7 + ... + n/n) which is approximately O(nlog(log(n))). Note that we skip over already established composite numbers as we know that we have already set all the multiples of that number. The space we used to store primes is O(n).

Now for some code to demonstrate this idea.

1from typing import List;
2
3def prime_sieve(n: int) -> List[int]:
4    primes = [True] * (n + 1)
5    primes[0] = primes[1] = False
6    for i in range (2, n + 1, 1):
7        if primes[i]:
8            for j in range (i + i, n + 1, i):
9                primes[j] = False;
10    return primes
11

1import java.util.Arrays;
2
3public static boolean [] primeSieve(int n) {
4    boolean [] primes = new boolean [n + 1];
5    Arrays.fill(primes, true);
6    primes[0] = primes[1] = false;
7    for (int i = 2; i <= n; i++) {
8        if (primes[i]) {
9            for (int j = i + i; j <= n; j += i) {
10                primes[j] = false;
11            }
12        }
13    }
14    return primes;
15}
16

1function primeSieve(n) {
2    const primes = Array(n + 1).fill(true);
3    primes[0] = primes[1] = false;
4    for (let i = 2; i <= n; i++) {
5        if (primes[i]) {
6            for (let j = i + i; j <= n; j += i) {
7                primes[j] = false;
8            }
9        }
10    }
11    return primes;
12}
13

1bool* prime_sieve(int n) {
2    bool primes[n + 1];
3    std::fill(primes, primes + n + 1, true);
4    primes[0] = primes[1] = false;
5    for (int i = 2; i <= n; i++) {
6        if (primes[i]) {
7            for (int j = i + i; j <= n; j += i) {
8                primes[j] = false;
9            }
10        }
11    }
12    return primes;
13}
14

If you are still struggling to understand the concept, it might be best to try the code out with an example with a random n on paper. Hopefully, this short article gives you some insight into the mathematical topics that will be covered in this section.