204. Count Primes

📝 Problem Details

• Title: 204. Count Primes
• Link: https://leetcode.com/problems/count-primes/
• Difficulty: Medium
• Tags/Categories: Math Arrays

💭What Were My Initial Thoughts?

Sieve of Eratosthenes~ https://www.geeksforgeeks.org/sieve-of-eratosthenes/

🤔What Did I Struggle With?

havent applied it before

💡 Explanation of Solution

every number can be divided into factors, and then those factors can be divided if necessary, all the way down until only prime factors are left.

- A vector `prime` is used to track whether a number is prime.
- Starting from `2`, the smallest prime, we mark all its multiples as non-prime.
- This process is repeated for all numbers up to the square root of `n` because all non-prime numbers will have been marked by then.
- Finally, the count of `true` values in the `prime` vector gives the number of primes less than `n`.

⌛ Complexity Analysis

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

Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) return 0; // No primes less than 2
 
        vector<bool> prime(n, true); // Initialize all numbers as prime
        prime[0] = prime[1] = false; // 0 and 1 are not prime
 
        for (int p = 2; p * p < n; p++) {
            if (prime[p]) {
                for (int i = p * p; i < n; i += p) {
                    prime[i] = false; // Mark multiples of p as non-prime
                }
            }
        }
 
        // Count primes
        return count(prime.begin(), prime.end(), true);
    }
};