algoadvance

Leetcode 204. Count Primes Sure, let’s break down the problem and proceed step by step.

Problem Statement

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

Clarifying Questions

Before implementing the solution, here are a few questions to clarify the requirements:

  1. What is the largest value of n we need to consider?
  2. Should we consider n itself as part of the range to check for primes?
  3. How optimal does the solution need to be in terms of time and space complexity?

Usually, these questions help to clearly understand the limitations and expectations. However, based on the typical problem constraints for LeetCode:

  1. The largest value of n is often less than 5 * 10^6.
  2. The problem statement specifies counting primes less than n, so n itself should not be considered.
  3. An efficient algorithm is preferred, likely sub-linear with respect to n.

Strategy

To solve this problem efficiently, we can use the Sieve of Eratosthenes algorithm, which is an efficient way to generate all prime numbers less than a given number n. The steps are as follows:

  1. Create a boolean array isPrime of size n, initialized to true. The index represents the number, and the value at that index indicates if the number is prime.
  2. Starting from the first prime number (2), mark all its multiples as false (i.e., not prime).
  3. Repeat the process for the next number in the array that is still marked as true.
  4. Continue this process until you’ve processed numbers up to the square root of n.
  5. Count the number of true values in the isPrime array, which gives the count of prime numbers less than n.

Code

Here’s the implementation in C++:

#include <vector>
#include <iostream>

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0; // No prime number less than 2

        std::vector<bool> isPrime(n, true);
        isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime numbers

        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;
    }
};

// Example usage
int main() {
    Solution solution;
    int n = 10; // Example input
    std::cout << "Number of primes less than " << n << ": " << solution.countPrimes(n) << std::endl;
    return 0;
}

Time Complexity

The time complexity of the Sieve of Eratosthenes algorithm is (O(n \log \log n)). This is because each prime number’s multiples are marked in (n / p) steps, where (p) is a prime number. The sum of the series for (p) over all primes is approximately (O(\log \log n)).

Space Complexity

The space complexity is (O(n)) due to the boolean array isPrime of size n.

This solution is both time-efficient and space-efficient for the problem constraints typically associated with LeetCode problems.

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