11.7 Count Primes

11.7.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 204
• Difficulty: Easy
• URL: https://leetcode.com/problems/lc-count-primes/
• Tags:
• Techniques: Dynamic Programming, Tabulation, Math, Sieve

11.7.2 Description

Return the number of prime numbers strictly less than n.

11.7.3 Examples

Input: n = 10
Output: 4   // 2,3,5,7

11.7.4 Constraints

• 0 <= n <= 5 * 10^6

11.7.5 Solution - Sieve of Eratosthenes

11.7.5.1 Walkthrough

Maintain a boolean array marking composite numbers. Starting from 2, whenever a number is unmarked (prime), mark all multiples starting at i * i as composite. Count the primes that remain unmarked below n.

11.7.5.2 Analysis

• Time Complexity: O(n log log n)
• Space Complexity: O(n)

11.7.5.3 Implementation Steps

1. If n < 2, return 0.
2. Create boolean isComposite[n].
3. For each i up to sqrt(n), if not composite, mark multiples i * i, i * i + i, ....
4. Count indexes with value false (primes).

11.7.5.4 Code - Java

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