{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Count Primes – Solution & Complexity

Interview solutions
/
Count Primes

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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)Add Two Numbers solution (medium)Climbing Stairs solution (easy)Excel Sheet Column Number solution (easy)Factorial solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?