How to Efficiently Count Prime Numbers

The definition of a prime number is simple: if a number can only be divided by 1 and itself, then it is a prime number.

Although the definition is easy, not many people can write efficient algorithms about primes.

For example, LeetCode Problem 204 "Count Primes" asks you to write this function:

// return the number of prime numbers in the interval [2, n)
int countPrimes(int n)

// for example, countPrimes(10) returns 4
// because 2, 3, 5, 7 are prime numbers

// return the number of prime numbers in the interval [2, n)
int countPrimes(int n);

// for example, countPrimes(10) returns 4
// because 2, 3, 5, 7 are prime numbers

# Return the number of prime numbers in the interval [2, n)
def countPrimes(n: int) -> int: 

# For example, countPrimes(10) returns 4
# because 2, 3, 5, 7 are prime numbers

// return the number of prime numbers in the interval [2, n)
func countPrimes(n int) int {
}

// for example, countPrimes(10) returns 4
// because 2, 3, 5, 7 are prime numbers

// return the number of prime numbers in the interval [2, n)
var countPrimes = function(n) {
};

// for example, countPrimes(10) returns 4
// because 2,3,5,7 are prime numbers

How would you write this function? Most people may write it like this:

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrime(i)) count++;
    return count;
}

// determine if the integer n is a prime
boolean isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            // has other divisors
            return false;
    return true;
}

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i < n; i++)
        if (isPrime(i)) count++;
    return count;
}

// determine if the integer n is a prime number
bool isPrime(int n) {
    for (int i = 2; i < n; i++)
        if (n % i == 0)
            // has other divisors
            return false;
    return true;
}

def countPrimes(n: int) -> int:
    count = 0
    for i in range(2, n):
        if isPrime(i):
            count += 1
    return count

# Determine if the integer n is a prime
def isPrime(n: int) -> bool:
    for i in range(2, n):
        if n % i == 0:
            # There are other divisors
            return False
    return True

func countPrimes(n int) int {
    count := 0
    for i := 2; i < n; i++ {
        if isPrime(i) {
            count++
        }
    }
    return count
}

// determine if the integer n is a prime number
func isPrime(n int) bool {
    for i := 2; i < n; i++ {
        if n % i == 0 {
            // has other divisors
            return false
        }
    }
    return true
}

var countPrimes = function(n) {
    var count = 0;
    for (var i = 2; i < n; i++) {
        if (isPrime(i)) count++;
    }
    return count;
};

// determine if the integer n is a prime number
var isPrime = function(n) {
    for (var i = 2; i < n; i++) {
        if (n % i === 0) {
            // has other divisors
            return false;
        }
    }
    return true;
}

This solution has time complexity O(n^2), which is not good. First, using an isPrime function is not efficient enough; and even if you use isPrime, the way you write it may have extra calculations.

Let’s talk about how to check if a number is prime. You only need to change the for loop in the isPrime function a little:

boolean isPrime(int n) {
    for (int i = 2; i * i <= n; i++)
        ...
}

In other words, i does not need to go up to n, just up to sqrt(n). Why? Let’s use n = 12 as an example.

12 = 2 × 6
12 = 3 × 4
12 = sqrt(12) × sqrt(12)
12 = 4 × 3
12 = 6 × 2

You can see, the last two multiplications are just the first two reversed. The turning point is at sqrt(n).

So, if you do not find a factor in [2, sqrt(n)], you can say n is a prime, because there are no more factors in [sqrt(n), n].

Now, the isPrime function runs in $O(sqrt(N))$ time. But to implement the countPrimes function, you actually do not need this function. The above explanation is just to help you understand sqrt(n), because we will use this idea later.

Efficient Implementation of countPrimes

Next, let's look at a method called the "Sieve of Eratosthenes." This method was invented by Eratosthenes, a famous ancient Greek. You may have seen his name in your school textbooks. He was the first to correctly calculate the Earth's circumference using the shadow of an object and is known as the "father of geography."

Back to the main topic. The core idea of the sieve method is the opposite of the usual approach:

Start from 2. We know 2 is a prime number. So, 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8... all these numbers cannot be primes.

Next, we see that 3 is also a prime. So, 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12... these numbers cannot be primes either.

This GIF from Wikipedia shows the process clearly:

By now, you should understand the logic of this elimination method. Let's look at the first version of the code:

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        // initialize the array to true
        Arrays.fill(isPrime, true);

        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                // multiples of i cannot be prime
                for (int j = 2 * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }
        
        return count;
    }
}

class Solution {
public:
    int countPrimes(int n) {
        // initialize the array to true
        vector<bool> isPrime(n, true);
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                // multiples of i cannot be prime
                for (int j = 2 * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countPrimes(self, n: int) -> int:
        # initialize the array to true
        isPrime = [True] * n
        for i in range(2, n):
            if isPrime[i]:
                # multiples of i cannot be prime
                for j in range(2 * i, n, i):
                    isPrime[j] = False

        count = 0
        for i in range(2, n):
            if isPrime[i]: 
                count += 1

        return count

func countPrimes(n int) int {
    isPrime := make([]bool, n)
    // initialize the array to true
    for i := 0; i < n; i++ {
        isPrime[i] = true
    }

    for i := 2; i < n; i++ {
        if isPrime[i] {
            // multiples of i cannot be prime
            for j := 2 * i; j < n; j += i {
                isPrime[j] = false
            }
        }
    }
    count := 0
    for i := 2; i < n; i++ {
        if isPrime[i] {
            count++
        }
    }
    return count
}

var countPrimes = function(n) {
    // initialize the array to true
    let isPrime = new Array(n).fill(true);
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) {
            // multiples of i cannot be prime
            for (let j = 2 * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    
    return count;
};

If you can understand the code above, you already know the main idea. But there are two small optimizations we can make.

First, remember the isPrime function from the start of this article. Because of the symmetry of factors, the for loop only needs to check [2, sqrt(n)]. Here, it's similar. The outer for loop only needs to go up to sqrt(n):

for (int i = 2; i * i < n; i++) 
    if (isPrime[i]) 
        ...

Besides this, there is another optimization in the inner for loop. Before, we wrote:

for (int j = 2 * i; j < n; j += i) 
    isPrime[j] = false;

This marks all multiples of i as false, but there is some repeated work.

For example, if n = 25 and i = 5, the algorithm marks 5 × 2 = 10, 5 × 3 = 15, and so on. But 10 and 15 have already been marked by i = 2 and i = 3 (2 × 5 and 3 × 5).

We can optimize this by letting j start from i * i instead of 2 * i:

for (int j = i * i; j < n; j += i) 
    isPrime[j] = false;

With this, the prime counting algorithm is efficient. This algorithm is called the Sieve of Eratosthenes. Here is the final complete code:

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i < n; i++)
            if (isPrime[i])
                for (int j = i * i; j < n; j += i)
                    isPrime[j] = false;

        int count = 0;
        for (int i = 2; i < n; i++)
            if (isPrime[i]) count++;

        return count;
    }
}

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> isPrime(n, true);
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countPrimes(self, n: int) -> int:
        isPrime = [True] * n
        for i in range(2, int(n ** 0.5) + 1):
            if isPrime[i]:
                for j in range(i * i, n, i):
                    isPrime[j] = False

        count = 0
        for i in range(2, n):
            if isPrime[i]: 
                count += 1

        return count

func countPrimes(n int) int {
    isPrime := make([]bool, n)
    for i := 0; i < n; i++ {
        isPrime[i] = true
    }

    for i := 2; i * i < n; i++ {
        if isPrime[i] {
            for j := i * i; j < n; j += i {
                isPrime[j] = false
            }
        }
    }
    count := 0
    for i := 2; i < n; i++ {
        if isPrime[i] {
            count++
        }
    }
    return count
}

var countPrimes = function(n) {
    let isPrime = new Array(n).fill(true);
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) count++;
    }
    
    return count;
};

The time complexity of this algorithm is a bit hard to calculate. It depends on the two nested for loops. The number of operations is roughly:

  n/2 + n/3 + n/5 + n/7 + ...
= n × (1/2 + 1/3 + 1/5 + 1/7...)

The part in brackets is the sum of the reciprocals of the prime numbers. The final result is $O(N * loglogN)$. If you are interested, you can look up the proof for the time complexity.

That's all for the prime number algorithm. As you can see, even simple problems can have many details to improve.