1- 问题描述
Count the number of prime numbers less than a non-negative number, n
2- 算法思想
给出要筛数值的范围 $n$，找出 $\sqrt{n}$ 以内的素数 $p_{1}, p_{2}, \cdots, p_{k}$。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。
3- Python实现
from math import sqrt def countPrimes(n):
if n in (0, 1, 2):
return 0
boards = [True] * n
boards[0] = boards[1] = False
for i in range(2, int(sqrt(n)) + 1):
for j in range(i * i, n, i):
boards[j] = False
primes = [i for i in boards if i]
return len(primes)
4- 实例