Count Primes

Medium Arrays & Hashing Math / Number Theory Original on LeetCode

Count Primes is a medium arrays & hashing problem solved with the math / number theory pattern. The best approach, optimal (sieve of eratosthenes), runs in O(n log log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (trial division) up.

Problem

Given an integer n, return how many prime numbers are strictly less than n.

A prime is a whole number greater than 1 whose only positive divisors are 1 and itself.

Examples

Example 1

Input
n = 20
Output
8
Why
The primes below 20 are 2, 3, 5, 7, 11, 13, 17 and 19.

Example 2

Input
n = 3
Output
1
Why
Only 2 is a prime strictly less than 3.

Example 3

Input
n = 1
Output
0
Why
There are no primes below 1.

Constraints

  • 0 <= n <= 5 * 10^6

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (trial division)O(n √n)O(1)
Optimal (Sieve of Eratosthenes)O(n log log n)O(n)

1Brute force (trial division)

TimeO(n √n)Each of the n numbers tries up to √n divisors.
SpaceO(1)Only a counter and loop variables.

Check every number from 2 to n - 1 on its own. A number m is prime when no d with d × d <= m divides it.

  1. For m from 2 to n - 1: try d = 2, 3, … while d × d <= m.
  2. If no d divides m, count it.
  3. Return the count.
class Solution {
    public int countPrimes(int n) {
        int count = 0;
        for (int m = 2; m < n; m++) {
            if (isPrime(m)) count++;
        }
        return count;
    }

    private boolean isPrime(int m) {
        for (int d = 2; (long) d * d <= m; d++) {
            if (m % d == 0) return false;
        }
        return true;
    }
}

2Optimal (Sieve of Eratosthenes)

TimeO(n log log n)Prime p crosses out about n / p numbers, and the sum of 1 / p over primes up to n grows like log log n.
SpaceO(n)One boolean per number below n.

Start by assuming every number from 2 to n - 1 is prime. Walk p upward; whenever p is still marked prime, cross out p × p, p × p + p, … up to n. Anything never crossed out is prime. Starting at p × p is safe because every smaller multiple of p has a smaller prime factor that already crossed it out.

  1. If n < 3, return 0.
  2. composite = boolean array of size n, all false.
  3. For p = 2 while p × p < n: if !composite[p], mark composite[j] for j = p × p, p × p + p, … < n.
  4. Count the indices 2 … n - 1 that are not composite.
class Solution {
    public int countPrimes(int n) {
        if (n < 3) return 0;
        boolean[] composite = new boolean[n];
        for (int p = 2; (long) p * p < n; p++) {
            if (composite[p]) continue;
            for (int j = p * p; j < n; j += p) composite[j] = true;
        }
        int count = 0;
        for (int m = 2; m < n; m++) {
            if (!composite[m]) count++;
        }
        return count;
    }
}

Edge cases to test

  • n = 0, 1 or 2: the answer is 0 (the bound is strict, so 2 itself is not counted when n = 2)
  • n is itself a prime: it must not be counted
  • The largest n, where testing every number one by one is too slow

Hints

Hint 1

To test one number m, you only need to try divisors up to √m. How expensive is that over all m < n?

Hint 2

Flip it around: instead of asking whether m has a divisor, let every prime cross out its own multiples.

Hint 3

When crossing out multiples of p, you can start at p × p, because smaller multiples were already crossed out by smaller primes.

FAQ

What is the best time complexity for Count Primes?

Optimal (Sieve of Eratosthenes) runs in O(n log log n) time and O(n) extra space. Prime p crosses out about n / p numbers, and the sum of 1 / p over primes up to n grows like log log n.

Which pattern does Count Primes use?

It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Reaching Points, Water and Jug Problem.

Is there a brute force solution for Count Primes?

Yes. Brute force (trial division) takes O(n √n) time and O(1) space. Check every number from 2 to n - 1 on its own.

Which edge cases should I test for Count Primes?

n = 0, 1 or 2: the answer is 0 (the bound is strict, so 2 itself is not counted when n = 2); n is itself a prime: it must not be counted; The largest n, where testing every number one by one is too slow.