LeetCode 204: Count Primes Solution

Problem Explanation

Explanation

To solve this problem, we can use the Sieve of Eratosthenes algorithm. The algorithm works by iteratively marking the multiples of each prime starting from 2 as composite numbers. After this process, the unmarked numbers left are prime numbers. We can count the number of prime numbers less than n using this algorithm.

Algorithm:

Initialize a boolean array isPrime of size n and set all values to true.
Start from 2 (first prime number) and iterate up to the square root of n.
For each prime number p, if isPrime[p] is true, mark all multiples of p as non-prime by setting isPrime[p*i] = false where i ranges from 2 to n/p.
Finally, count the number of true values in the isPrime array, excluding 0 and 1.

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

Solution Code

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, 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;
    }
}

Frequently Asked Questions

How to solve LeetCode 204 (Count Primes)?

This page provides optimized solutions for LeetCode problem 204 (Count Primes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 204 (Count Primes)?

The time complexity for LeetCode 204 (Count Primes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 204 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 204 in Java, C++, or Python.