How to Efficiently Count Prime Numbers

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

Although the definition of prime numbers is not complicated, few people can write efficient algorithms related to prime numbers.

For example, LeetCode problem #204 "Count Primes" asks you to write a function like this:

// 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? I think most of you would 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;
};

var isPrime = function(n) {
    for (var i = 2; i < n; i++) {
        if (n % i === 0) {
            // has other divisors
            return false;
        }
    }
    return true;
}

Writing it this way results in a time complexity of O(n^2), which is a significant issue. Firstly, using the isPrime function as an auxiliary approach is not efficient; moreover, even if you use the isPrime function, this algorithm still suffers from redundant calculations.

Let's discuss how you should write an algorithm to determine if a number is a prime. You only need to slightly modify the for loop condition in the above isPrime code:

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

In other words, i does not need to iterate up to n, but only up to sqrt(n). Why is this? Let's take an example, assume n = 12.

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

As you can see, the last two products are the reverse of the first two, with the critical point of reversal at sqrt(n).

In other words, if no divisible factor is found within the interval [2, sqrt(n)], we can directly conclude that n is a prime number since no divisible factors will be found in the interval [sqrt(n), n].

Now, the time complexity of the isPrime function is reduced to $O(sqrt(N))$. However, we do not actually need this function to implement the countPrimes function. The above explanation is provided to help readers understand the significance of sqrt(n), as it will be used again shortly.

Efficient Implementation of countPrimes

The following method is known as the "Sieve of Eratosthenes," invented by a great ancient Greek named Eratosthenes. We have seen his name in our middle school textbooks because he was the first to correctly calculate the Earth's circumference using the shadow of an object and is acclaimed as the "Father of Geography."

Back to the main topic, the core idea of the Sieve of Eratosthenes is the reverse of the conventional approach mentioned earlier:

Starting from 2, we know 2 is a prime number, so 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8... none of these can be prime numbers.

Then we find that 3 is also a prime number, so 3 × 2 = 6, 3 × 3 = 9, 3 × 4 = 12... none of these can be prime numbers either.

This GIF from Wikipedia illustrates it well:

At this point, do you somewhat understand the logic of this elimination method? Let's look at our 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) {
        vector<bool> isPrime(n, true);
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                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:
        isPrime = [True] * n
        for i in range(2, n):
            if isPrime[i]:
                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)
    for i := 0; i < n; i++ {
        isPrime[i] = true
    }

    for i := 2; i < n; i++ {
        if isPrime[i] {
            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) {
    let isPrime = new Array(n).fill(true);
    for (let i = 2; i < n; i++) {
        if (isPrime[i]) {
            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've grasped the overall idea, but there are still two subtle optimizations you can make.

First, recall the isPrime prime-checking function introduced at the beginning of this article. Due to the symmetry of factors, the for loop only needs to iterate through [2, sqrt(n)]. Similarly, our outer for loop also only needs to iterate up to sqrt(n):

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

Additionally, it's hard to notice that the inner for loop can also be optimized. Our previous approach was:

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

This marks all multiples of i as false, but there is still some redundant computation.

For example, when n = 25 and i = 5, the algorithm marks 5 × 2 = 10, 5 × 3 = 15, etc., but these numbers have already been marked by i = 2 and i = 3 as 2 × 5 and 3 × 5.

We can slightly optimize this by starting j 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 efficiently implemented. Actually, this algorithm has a name: Sieve of Eratosthenes. Here is the complete final 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 quite challenging to calculate. It is evidently related to the two nested for loops, with the number of operations being:

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

The expressions in the parentheses are the reciprocals of prime numbers. The final result is $O(N * \log\log N)$. Readers interested in the proof of this time complexity can look it up.

This concludes all the content related to the prime number algorithm. How is it? Even seemingly simple problems have many details that can be refined!