DSA problem
Count Primes
Given an integer n, return the number of prime numbers that are strictly less than n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
The simplest correct algorithm tests each candidate i in [2, n) for primality by trial division up to sqrt(i). That works but is O(n * sqrt(n)) total, which is too slow when n is close to 5 * 10^6.
The Sieve of Eratosthenes is the textbook accelerator. Allocate a boolean array isPrime[0..n - 1] initially all true, then mark 0 and 1 as not prime. For each i from 2 up to sqrt(n), if isPrime[i] is still true, mark all multiples i * i, i * i + i, i * i + 2i, ... up to n - 1 as not prime. Any smaller multiple of i was already crossed off by a smaller prime factor, so we can start marking at i * i for efficiency.
After the sieve finishes, simply count how many entries of isPrime remain true in [2, n). The total work to mark composites is n / 2 + n / 3 + n / 5 + ... = O(n log log n) by the famous bound on the harmonic sum over primes, and the memory is O(n) for the sieve array. This is the canonical answer to "count primes below n" and is fast enough for n up to a few tens of millions.
Examples
n = 104n = 00n = 10Constraints
- 0 <= n <= 5 * 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.