Sieve of Eratosthenes

Problem

Count how many prime numbers are strictly less than n using the sieve of Eratosthenes.

Start with every number marked prime, then for each prime p mark its multiples starting from p squared as composite. Return 0 for n < 3; for example count_primes(10) is 4.

Hint

Only sieve with primes up to sqrt(n); composite numbers below that are already marked.

Test cases

case 1

in: [10]

expected: 4

case 2

in: [2]

expected: 0

case 3

in: [0]

expected: 0

case 4

in: [1]

expected: 0

case 5

in: [100]

expected: 25

Starter codePython

def count_primes(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor