algoadvance

Leetcode 204. Count Primes

Problem Statement

Leetcode Problem 204: Count Primes

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

Clarifying Questions

  1. Input Constraints:
    • What is the range of the input integer n?
      • Solution: The input integer ( n ) is in the range ([0, 5 \times 10^6]).
  2. Edge Cases:
    • How should the function handle values of n less than or equal to 2?
      • Solution: Return 0 since there are no prime numbers less than 2.
  3. Performance:
    • Is there an efficient algorithm since the brute-force solution might not be feasible for large ( n )?
      • Solution: Yes, we should consider using the Sieve of Eratosthenes for an optimal solution.

Strategy

To count the number of prime numbers less than ( n ), we can use the Sieve of Eratosthenes technique:

  1. Initialize: Create a boolean array isPrime of size ( n ) where each entry isPrime[i] will be true if i is a prime number, initially assuming all numbers are prime.
  2. Mark Non-Primes: We will iterate through the numbers starting from 2. For each number p that is still marked as prime, mark all multiples of p (starting from ( p \times p )) as non-prime.
  3. Count Primes: The number of true values in the isPrime array from index 2 to ( n-1 ) will give the count of prime numbers less than ( n ).

Code

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

        boolean[] isPrime = new boolean[n];
        // Initialize all entries as true, except for index 0 and 1 which are not primes
        for (int i = 2; i < n; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        int count = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) count++;
        }

        return count;
    }

    public static void main(String[] args) {
        CountPrimes cp = new CountPrimes();
        System.out.println(cp.countPrimes(10));  // Output: 4 (2, 3, 5, 7)
        System.out.println(cp.countPrimes(0));   // Output: 0
        System.out.println(cp.countPrimes(1));   // Output: 0
    }
}

Time Complexity

The time complexity of the Sieve of Eratosthenes algorithm is ( O(n \log \log n) ) because each prime number’s multiples are marked in approximately ( O(\log \log n) ) operations. This is a near-linear time complexity, making it efficient for large values of ( n ).

Edge Cases

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI