Problem statement

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

A prime is a whole number greater than 1 whose only divisors are 1 and itself.

Example 1

Input: n = 10
Output: 4
Explanation: The primes below 10 are 2, 3, 5 and 7.

Example 2

Input: n = 0
Output: 0

Example 3

Input: n = 2
Output: 0
Explanation: 2 itself is excluded — the bound is strict.

Constraints

• 0 <= n <= 800

Follow-up: Testing each number for primality is O(n·√n). Can you do it in O(n log log n)?

Hints for Count Primes

1. Hint 1

   Testing every candidate separately repeats work. Instead, cross out multiples.

2. Hint 2

   Sieve of Eratosthenes: walk i upward from 2; the first time you reach an uncrossed i it must be prime, so cross out i·i, i·i + i, i·i + 2i, …

3. Hint 3

   Start crossing at i·i, not 2i — every smaller multiple of i already carries a smaller prime factor and is gone.

How to solve Count Primes

Instead of testing each candidate for primality, cross out every composite below n with the Sieve of Eratosthenes: each prime knocks out all of its multiples in one sweep.

Approach

1. Return 0 when n < 3 — there are no primes below 2.
2. Allocate a boolean array of size n, all true, and mark 0 and 1 as not prime.
3. For i from 2 while i * i < n: if i is still marked prime, mark i·i, i·i + i, i·i + 2i, … as composite.
4. Count the entries still marked true.

Why it works

When the loop reaches an unmarked i, no smaller number divides it, so it is prime. Every composite c < n has a prime factor p ≤ √c, and that prime's pass marks c. Starting at i·i is safe because any smaller multiple k·i with k < i was already crossed by one of k's prime factors.

Complexity

• Time — O(n log log n)
• Space — O(n)

Pitfalls

• The question asks for primes strictly less than n — size the sieve to n, not n + 1.
• Trial-dividing each number up to √n is O(n√n) and times out for n near 5·10⁶.

Reference solution

Python

def countPrimes(n: int) -> int:
    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)

Java

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

C++

int countPrimes(int n) {
    if (n < 3) return 0;
    vector<char> sieve(n, 0);
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!sieve[i]) {
            count++;
            for (long long j = (long long) i * i; j < n; j += i) sieve[j] = 1;
        }
    }
    return count;
}

JavaScript

var countPrimes = function(n) {
    if (n < 3) return 0;
    const sieve = new Uint8Array(n);
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (sieve[i] === 0) {
            count++;
            for (let j = i * i; j < n; j += i) sieve[j] = 1;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Double a Number Represented as a Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium