素数个数统计——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实现

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

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

上一篇:数据导出为excel表格


下一篇:css3技巧——产品列表之鼠标滑过效果(一)