204. Count Primes

Description

Given an integer n, the task is to return the number of prime numbers that are strictly less than n. Prime numbers are numbers greater than 1 that have no divisors other than 1 and themselves.

Intuition

The problem can be efficiently solved using the Sieve of Eratosthenes algorithm, which systematically marks the multiples of each prime number starting from 2. By the end of this process, all numbers that are still unmarked are prime. The key idea is to minimize unnecessary calculations and prevent overflow by handling large numbers carefully.

Approach

1. Initialization: - Create a boolean array seen of size n, initialized to false. This array will keep track of which numbers have been marked as non-prime. - Initialize a counter ans to zero, which will store the number of primes found.
2. Outer Loop (Iterate Through Potential Primes): - Iterate through numbers from 2 to n-1. - If a number has not been marked (seen[num] == false), it is a prime, so increment ans. - Before marking multiples, ensure that num * num does not exceed n to avoid overflow.
3. Inner Loop (Mark Multiples): - For each prime num, start marking multiples of num beginning from num * num. - Set seen[mult] = true for each multiple to indicate that it is not a prime.
4. Return Result: - After the loops complete, return the value of ans, which represents the count of prime numbers less than n.

Complexity

Time Complexity:

O(n log log n), which is the time complexity of the Sieve of Eratosthenes. The outer loop runs in O(n) time, but marking multiples (inner loop) for each prime runs in O(log log n) time on average.

Space Complexity:

O(n), as we use an array of size n to keep track of whether each number is prime.

Code

C++

class Solution {
public:
    int countPrimes(int n) {
        if (n < 2) return 0;

        vector seen(n, false);
        int ans = 0;

        for (int num = 2; num < n; num++) {
            if (seen[num]) continue;
            ans++;
            if (num > sqrt(n)) continue;  // Prevent overflow
            for (int mult = num * num; mult < n; mult += num) {
                seen[mult] = true;
            }
        }

        return ans;
    }
};

Python

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0

        seen = [False] * n
        ans = 0

        for num in range(2, n):
            if seen[num]:
                continue
            ans += 1
            for mult in range(num * num, n, num):
                seen[mult] = True

        return ans

Java

class Solution {
    public int countPrimes(int n) {
        if (n < 2) return 0;

        boolean[] seen = new boolean[n];
        int ans = 0;

        for (int num = 2; num < n; num++) {
            if (seen[num]) continue;
            ans++;
            if ((long)num * num >= n) continue;  // Prevent overflow
            for (int mult = num * num; mult < n; mult += num) {
                seen[mult] = true;
            }
        }

        return ans;
    }
}

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {

    let seen = new Uint8Array(n), ans = 0
    for (let num = 2; num < n; num++) {
        
        if (seen[num]) continue
        ans++
        for (let mult = num * num; mult < n; mult += num)
            seen[mult] = 1
    }
    return ans
};