Given an integer n, return how many prime numbers are strictly less than n. A prime is a number greater than 1 whose only divisors are 1 and itself.
- 0 <= n <= 5 * 10^6
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force checks every number below n for divisors up to its square root, which is O(n * sqrt(n)). The Sieve of Eratosthenes flips the work around: assume everything from 2 is prime, then for each prime p, cross out all its multiples. A number that is never crossed out has no smaller prime factor, so it is prime. Two speed ups: only sieve with p while p * p < n, and start crossing out at p * p, since a smaller multiple k * p with k < p was already crossed out by the prime factor of k. The total work is O(n log log n), which is almost linear.
Algorithm
- If
n < 3, return 0. - Make a boolean array
isPrimeof sizen, all true, and set indices 0 and 1 to false. - For
pfrom 2 whilep * p < n: ifisPrime[p], markp*p, p*p + p, ...belownas false. - Return the number of true values.
O(n log log n)Space: O(n)n, so n = 2 gives 0. In Java and C++, write the loop condition as (long) p * p < n or p <= n / p to avoid overflow for large n.class Solution: def countPrimes(self, n: int) -> int: if n < 3: return 0 is_prime = bytearray([1]) * n is_prime[0] = is_prime[1] = 0 p = 2 while p * p < n: if is_prime[p]: # cross out multiples starting at p * p (slice assignment is fast) is_prime[p * p::p] = bytes(len(range(p * p, n, p))) p += 1 return sum(is_prime)