{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Count Primes – Solution & Complexity

Interview solutions
/
Count Primes

1. Understand the Pattern

  • We need every prime below n, not including n itself.
  • Checking each number independently repeats a lot of work.
  • A sieve marks composite numbers once and counts what remains.

2. Handle the Tiny Cases

  • If n is 0, 1, or 2, there are no primes below it.
  • Return 0 immediately for those inputs.
  • This also lets the sieve assume n >= 3.
def count_primes(n):
    if n < 3:
        return 0

3. Sieve of Eratosthenes

  • Assume every number from 2 to n-1 is prime.
  • For each prime p, cross out its multiples starting at p * p.
  • Anything still marked prime at the end is counted.
def count_primes(n):
    if n < 3:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p < n:
        if is_prime[p]:
            for multiple in range(p * p, n, p):
                is_prime[multiple] = False
        p += 1
    return sum(is_prime)

4. Final Solution and Complexity

  • Starting at p * p is safe because smaller multiples were already crossed out by smaller primes.
  • Time complexity is O(n log log n).
  • Space complexity is O(n) for the boolean sieve.
def count_primes(n: int) -> int:
    if n < 3:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p < n:
        if is_prime[p]:
            for multiple in range(p * p, n, p):
                is_prime[multiple] = False
        p += 1
    return sum(is_prime)

FAQ

See also

Practice Count Primes online (run code in the browser)Climbing Stairs solution (easy)Excel Sheet Column Number solution (easy)Factorial solution (easy)Fibonacci Number solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?