184. Count Primes
Your function receives a single integer n and returns how many prime numbers are strictly less than n.
A prime is an integer greater than 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11, … Note the strictly less than — if n itself is prime, it does not count. For n = 0, 1, or 2 there are no primes below n, so the answer is 0.
Checking each number one by one works, but the interesting question is how to count them all at once when n gets large.
Example 1:
Input: n = 10
Output: 4
Explanation: The primes below 10 are 2, 3, 5, and 7 — four of them.
Example 2:
Input: n = 2
Output: 0
Explanation: The smallest prime is 2, and the count is over numbers strictly below n, so nothing qualifies.
Constraints:
- 0 ≤ n ≤ 10⁶
Hints:
You can test a single number x for primality by trying divisors only up to √x — any factor pair has one member at or below the square root. Counting this way is correct but does redundant work for every candidate.
Flip the direction: instead of asking 'is x prime?' for each x, let each prime *cross out* all of its multiples. Start a boolean array as all-prime, and for each p starting at 2, mark 2p, 3p, … as composite. Begin the marking at p·p — every smaller multiple was already crossed out by a smaller factor.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 10
Expected output: 4