204. Count Primes

Medium

Problem Description

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

Examples

Example 1:
Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:
Input: n = 0
Output: 0

Example 3:
Input: n = 1
Output: 0
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def countPrimes(n: int) -> int:
    if n <= 2:
        return 0
    
    # Initialize array with True values
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    
    # Use Sieve of Eratosthenes
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            # Mark multiples as non-prime
            is_prime[i * i:n:i] = [False] * len(is_prime[i * i:n:i])
    
    return sum(is_prime)

Memory-Optimized Solution:


def countPrimes(n: int) -> int:
    if n <= 2:
        return 0
    
    # Use bit array for memory optimization
    is_prime = bytearray([1]) * ((n + 7) // 8)
    count = n - 2  # Start with count of all numbers except 0 and 1
    
    def get_bit(num):
        return bool(is_prime[num // 8] & (1 << (num % 8)))
    
    def clear_bit(num):
        is_prime[num // 8] &= ~(1 << (num % 8))
    
    for i in range(2, int(n ** 0.5) + 1):
        if get_bit(i):
            for j in range(i * i, n, i):
                if get_bit(j):
                    clear_bit(j)
                    count -= 1
    
    return count

Java Solution


class Solution {
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        
        // Initialize array with true values
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        // Use Sieve of Eratosthenes
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                // Mark multiples as non-prime
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // Count prime numbers
        int count = 0;
        for (boolean prime : isPrime) {
            if (prime) {
                count++;
            }
        }
        return count;
    }
}

C++ Solution


class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        
        // Use vector for memory optimization
        vector isPrime(n, true);
        isPrime[0] = isPrime[1] = false;
        
        // Use Sieve of Eratosthenes
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                // Mark multiples as non-prime
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        return count(isPrime.begin(), isPrime.end(), true);
    }
};

JavaScript Solution


/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    if (n <= 2) {
        return 0;
    }
    
    // Initialize array with true values
    const isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;
    
    // Use Sieve of Eratosthenes
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            // Mark multiples as non-prime
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    return isPrime.filter(Boolean).length;
};

C# Solution


public class Solution {
    public int CountPrimes(int n) {
        if (n <= 2) {
            return 0;
        }
        
        // Initialize array with true values
        bool[] isPrime = new bool[n];
        Array.Fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        
        // Use Sieve of Eratosthenes
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                // Mark multiples as non-prime
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        return isPrime.Count(x => x);
    }
}

Complexity Analysis

Solution Explanation

The solution uses the Sieve of Eratosthenes algorithm:

Key Points

Common Pitfalls

Further Optimizations