Primes Below A Limit
Problem
Count how many prime numbers are strictly smaller than a given limit. The limit can reach a few million, so testing each candidate against its divisors is far too slow.
Examples
Input: limit = 10
Output: 4
Why: 2, 3, 5 and 7Input: limit = 100
Output: 25Input: limit = 2
Output: 0
Why: edge case, nothing below 2 is primeHints
0 / 3
Testing one number at a time repeats work: the same small factors get tried over and over across the whole range.
Turn the question around. Instead of asking what divides a candidate, ask what each small number can reach.
Keep a flag per value in the range. Walk upwards, and whenever a value is still flagged as possible, clear the flags on its multiples starting from its square. Stop the outer walk once the value passes the square root of the limit, and count the flags that survive.
Solution
Flag every value as a candidate, then walk upwards clearing the multiples of each survivor. A survivor has no smaller factor, which is exactly what makes it prime, so nothing is ever tested for divisibility. The inner clearing can start at the square of the value, because anything smaller carries a smaller factor that already cleared it, and the outer walk can stop at the square root of the limit for the same reason. Time is O(n log log n) and space is O(n) flags.
def count_primes(limit):
if limit < 3:
return 0 # nothing below 2 is prime
ok = [True] * limit
ok[0] = ok[1] = False
for p in range(2, int(limit ** 0.5) + 1):
if ok[p]: # p survived, so p is prime
step = len(range(p * p, limit, p))
ok[p * p:limit:p] = [False] * step
return sum(ok)
print(count_primes(10)) # -> 4
print(count_primes(100)) # -> 25
print(count_primes(2)) # -> 0
print(count_primes(3)) # -> 1Stuck on the idea rather than the code? Sieve of Eratosthenes covers it.