NeetCode #936LC-204MediumMath & Geometry
← Back to All Problems#936 · #204 · Count Primes(计数质数)
📌 Problem Statement & Constraints
Given an integer
n, return the number of prime numbers strictly less than n. Constraints: 0 <= n <= 5 * 10^6.💡 Core Algorithmic Approaches
- Use the Sieve of Eratosthenes: mark multiples of each prime as composite in a boolean array.
- Only iterate the outer loop up to
sqrt(n); larger composites already have a smaller prime factor. - Start marking at
i * i, since all smaller multiples ofiwere already crossed off by smaller primes. - Count the entries still marked prime.
💻 Benchmark Python3 Implementation
class Solution:
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n, i): # start at i*i
is_prime[j] = False
return sum(is_prime)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log log n): the harmonic-sum bound of the sieve.
💾 Space Complexity
O(n): the boolean array.
⚠️ Interview Pitfalls & Follow-ups
- Trial-dividing every number: O(n sqrt(n)) times out for
n = 5 * 10^6. - Starting the inner loop at
2 * i: it re-marks many composites;i * iis the correct start. - Iterating the outer loop to
n: onlysqrt(n)is needed. - Skipping the
n < 3guard: forn <= 1the assignmentis_prime[1] = Falsewould be out of range. - Returning the count for values at most
n: the problem asks for primes strictly belown.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.