素数个数统计——Eratosthenes筛法 [LeetCode 204]

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实现

 1 from math import sqrt
 2  
 3 def countPrimes(n):
 4     if n in (0, 1, 2):    
 5         return 0
 6     boards = [True] * n
 7     boards[0] = boards[1] = False
 8     for i in range(2, int(sqrt(n)) + 1):
 9         for j in range(i * i, n, i):
10             boards[j] = False
11     primes = [i for i in boards if i]
12     return len(primes)

4- 实例