How to Efficiently Count Prime Numbers
This article will resolve
LeetCode | Difficulty |
---|---|
204. Count Primes | 🟠 |
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 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;
};
Algorithm Visualization
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 . 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.
Related Problems
You can install my Chrome extension then open the link.
LeetCode | Difficulty |
---|---|
264. Ugly Number II | 🟠 |