⚡Flashcard Drill➔
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

  1. Use the Sieve of Eratosthenes: mark multiples of each prime as composite in a boolean array.
  2. Only iterate the outer loop up to sqrt(n); larger composites already have a smaller prime factor.
  3. Start marking at i * i, since all smaller multiples of i were already crossed off by smaller primes.
  4. 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 * i is the correct start.
  • Iterating the outer loop to n: only sqrt(n) is needed.
  • Skipping the n < 3 guard: for n <= 1 the assignment is_prime[1] = False would be out of range.
  • Returning the count for values at most n: the problem asks for primes strictly below n.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems