Free Math and bits lessonsMath and bits · Stage 1 · Primes and remainders · Step 1

Cross out the multiples

Find every prime below n at once with the sieve of Eratosthenes. About 10 minutes.

Assume prime, then cross out

Picture raffle tickets numbered from 2 upward, all still in the running. Take the first ticket still in, 2, and scratch out all its multiples, since they cannot be prime. The next ticket still standing, 3, must be prime, so scratch out its multiples too.

Keep going, and whatever survives is prime.

Still standing when you reach it: means prime.

Primes below n = 30 (· = crossed out)

2 is prime. Cross out its multiples from 2 × 2 = 4: 4, 6, 8, …

Move 1 of 4

Start at p × p

When you cross out the multiples of a prime p, the ones below p times p were already crossed out by smaller primes. For p = 5, the numbers 10, 15 and 20 fell to 2 and 3, so start at 25.

And once p times p passes n, nothing new would fall, so you can stop early.

0 and 1: are not prime; mark them out first.

In code

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 m in range(p * p, n, p):
            is_prime[m] = False
    p += 1
return sum(is_prime)

Quick check

When the sieve reaches 5, which multiple of 5 is the first it needs to cross out?

Show the answer

25. 10, 15 and 20 were already crossed by 2 or 3.

Your problem

Count the primes

Return how many prime numbers are less than n.

Example

n = 10 → 4

0 ≤ n ≤ 5,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.