Leetcode Problem 204. Count Primes

204. Count Primes

Leetcode Solutions

Key approach of the solution: Sieve of Eratosthenes

  1. Initialize an array isPrime of length n with True (except for indices 0 and 1 which are False).
  2. Start with the first prime number, p = 2.
  3. Use a nested loop where the outer loop runs from 2 to sqrt(n) and the inner loop marks the multiples of p as False.
  4. In the inner loop, start marking from p*p up to n in increments of p.
  5. After marking the multiples of p, find the next number greater than p that is not marked and set p to this new number.
  6. Repeat steps 3-5 until p exceeds sqrt(n).
  7. Count the number of True values in the isPrime array, which represents the number of primes less than n.
UML Thumbnail

Alternative approach: Brute-force Prime Checking

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...