MediumArrayMathNumber Theory

Count Primes

1 approach, code in every language

Given an integer n, count 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.

For small inputs a divisibility test per candidate is fine, but as n grows you want a method that shares work across candidates rather than testing each number in isolation.

Example 1

Input: n = 10

Output: 4

The primes below 10 are 2, 3, 5, and 7, which is four values.

Example 2

Input: n = 2

Output: 0

There are no primes strictly less than 2, so the answer is 0.

Constraints

0 <= n <= 5 * 10^6
The count includes only primes strictly less than n

Sieve of Eratosthenes

Mark the multiples of each discovered prime as composite, then count the numbers that were never marked.

Loading animation…

Intuition

Instead of testing each number for primality on its own, flip the problem around and cross out composites. Keep a boolean array over the range and, for each number that is still unmarked when you reach it, treat it as prime and strike out all of its multiples. Starting the strike-out at the square of the prime avoids redundant work, since any smaller multiple already carries a smaller prime factor that marked it earlier. Whatever survives the sweep is prime.

Algorithm walkthrough

1If n is less than 3 there are no primes below it, so return 0 right away.
2Create a boolean array composite of length n, all initially false.
3Scan i from 2 up to n - 1; whenever composite[i] is still false, count it as prime.
4For each such prime i, mark every multiple starting at i * i up to n - 1 as composite.
5Return the running count of unmarked numbers.

Implementation

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0
        composite = [False] * n
        count = 0
        for i in range(2, n):
            if not composite[i]:
                count += 1
                for multiple in range(i * i, n, i):
                    composite[multiple] = True
        return count

Time

O(n log log n)

Space

O(n)

The sieve's total marking work sums to n over the reciprocals of primes, giving the classic log-log bound.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Indivisible Catalogue Numbers is our own problem on the technique behind Count Primes: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free