Approach: Sieve of Eratosthenes

def countPrimes(n):
    if n < 3: return 0
    sieve = [True]*n
    sieve[0] = sieve[1] = False
    i = 2
    while i*i < n:
        if sieve[i]:
            for j in range(i*i, n, i):
                sieve[j] = False
        i += 1
    return sum(sieve)

Complexity: O(n log log n) time, O(n) space.

Full Solution — all languages

class Solution:
    def countPrimes(self, n):
        if n < 3:
            return 0
        sieve = [True] * n
        sieve[0] = sieve[1] = False
        i = 2
        while i * i < n:
            if sieve[i]:
                for j in range(i * i, n, i):
                    sieve[j] = False
            i += 1
        return sum(sieve)

import java.util.*;
class Solution {
    public int countPrimes(int n) {
        if (n < 3) return 0;
        boolean[] comp = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!comp[i]) {
                count++;
                for (long j = (long) i * i; j < n; j += i) comp[(int) j] = true;
            }
        }
        return count;
    }
}

#include <bits/stdc++.h> using namespace std;
class Solution {
    public: int countPrimes(int n) {
        if (n < 3) return 0;
        vector<bool> comp(n, false);
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!comp[i]) {
                count++;
                for (long long j = (long long) i * i; j < n; j += i) comp[j] = true;
            }
        }
        return count;
    }
};

/**
 * @param {number} n
 * @return {number}
 */ var countPrimes = function(n) {
    if (n < 3) return 0;
    const comp = new Array(n).fill(false);
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (!comp[i]) {
            count++;
            for (let j = i * i; j < n; j += i) comp[j] = true;
        }
    }
    return count;
};

Count Primes

Example 1

Example 2

Example 3

Constraints