Coding problem · Medium · Basics

Count Primes Below n

Medium Algorithms & data structures

Return how many prime numbers are strictly less than n. 0 <= n <= 100000.

Example 1

Input: n = 10
Output: 4
Explanation: 2, 3, 5 and 7

Example 2

Input: n = 2
Output: 0

Hints

Hint 1

Testing every number with is-prime works but is slow for big n.

Hint 2

Sieve of Eratosthenes: mark multiples of each prime as not prime, starting from p × p.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n log log n) · Space O(n)

Create a boolean array, then for each p from 2 while p * p < n, if p is still marked prime, mark p*p, p*p+p, ... as composite. Count what's left. O(n log log n).

Reference solution

function countPrimes(n) {
  if (n < 3) return 0;
  const prime = new Array(n).fill(true);
  prime[0] = prime[1] = false;
  for (let p = 2; p * p < n; p++) if (prime[p]) for (let m = p * p; m < n; m += p) prime[m] = false;
  return prime.filter(Boolean).length;
}

function countPrimes(n: number): number {
  if (n < 3) return 0;
  const prime = new Array<boolean>(n).fill(true);
  prime[0] = prime[1] = false;
  for (let p = 2; p * p < n; p++) if (prime[p]) for (let m = p * p; m < n; m += p) prime[m] = false;
  return prime.filter(Boolean).length;
}

def count_primes(n: int) -> int:
    if n < 3:
        return 0
    prime = [True] * n
    prime[0] = prime[1] = False
    p = 2
    while p * p < n:
        if prime[p]:
            for m in range(p * p, n, p):
                prime[m] = False
        p += 1
    return sum(prime)

<?php

function countPrimes(int $n): int
{
    if ($n < 3) {
        return 0;
    }
    $prime = array_fill(0, $n, true);
    $prime[0] = $prime[1] = false;
    for ($p = 2; $p * $p < $n; $p++) {
        if ($prime[$p]) {
            for ($m = $p * $p; $m < $n; $m += $p) {
                $prime[$m] = false;
            }
        }
    }
    return count(array_filter($prime));
}

class Solution {
    public int countPrimes(int n) {
        if (n < 3) return 0;
        boolean[] composite = new boolean[n];
        int count = 0;
        for (int p = 2; p < n; p++) {
            if (composite[p]) continue;
            count++;
            for (long m = (long) p * p; m < n; m += p) composite[(int) m] = true;
        }
        return count;
    }
}

Was this page helpful?