Count Primes — Sieve of Eratosthenes O(n log log n) [Amazon Easy]

Problem Statement

Given an integer n, return the number of prime numbers strictly less than n.

Input: n = 10 → 4 (primes: 2, 3, 5, 7) Input: n = 0 → 0 Input: n = 1 → 0

Intuition — Sieve of Eratosthenes
C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity

Intuition — Sieve of Eratosthenes

Create a boolean array is_prime[0..n-1]. Mark all entries true. Then for every prime p starting from 2, mark all multiples of p (starting from p²) as not prime.

Why start from p²? All smaller multiples of p (like 2p, 3p...) have already been marked by smaller primes.

Complexity: O(n log log n) — asymptotically nearly linear.

C Solution

int countPrimes(int n) {
    if (n < 2) return 0;
    char* is_prime = calloc(n, 1);
    memset(is_prime, 1, n);
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; (long long)i * i < n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < n; j += i) {
                is_prime[j] = 0;
            }
        }
    }
    int count = 0;
    for (int i = 2; i < n; i++) count += is_prime[i];
    free(is_prime);
    return count;
}

C++ Solution

#include <vector>
using namespace std;

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

Java Solution

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

JavaScript Solution

function countPrimes(n) {
    if (n < 2) return 0;
    const isPrime = new Uint8Array(n).fill(1);
    isPrime[0] = isPrime[1] = 0;
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) isPrime[j] = 0;
        }
    }
    return isPrime.reduce((s, v) => s + v, 0);
}

Python Solution

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2: return 0
        is_prime = bytearray([1]) * n
        is_prime[0] = is_prime[1] = 0
        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:
                is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))
        return sum(is_prime)

Complexity

	Time	Space
Sieve	O(n log log n)	O(n)

Memory optimization: Sieve of Sundaram or bitset sieve can reduce space to O(n/8).