Count Primes
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Given an integer n, return how many prime numbers are strictly less than n. Testing each number individually for primality is too slow at the upper limit.
Examples
Constraints
- • 0 <= n <= 5·10^6
Hints & approach
Hint 1
Instead of testing numbers, cross out the ones that cannot be prime.
Hint 2
Every multiple of a prime p (other than p) is composite.
Hint 3
Start crossing out at p·p and only loop p up to √n.
Approachtry the hints first
Use the Sieve of Eratosthenes. Allocate a boolean array of size n marked prime, then clear 0 and 1. For each p from 2 while p·p < n, if p is still marked, mark p·p, p·p + p, … as composite; smaller multiples were already removed by smaller primes. Count the entries still marked.
Time O(n log log n) · Space O(n)
