计数质数 Python 埃氏筛选法
题目
题目链接：
统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
提示：
-
0 <= n <= 5 * 106
解题
思路分析
暴力枚举
这道题暴力枚举，就是依次判断这个数是不是质数，如果是，就+1。这种思路便于理解，但是太慢了，本题不做过多赘述
代码
import functools
import math
class Solution:
def countPrimes(self, n: int) -> int:
@functools.lru_cache()
def isPrime(num):
if num <= 3:
return num >= 2
if (num + 1) % 6 != 0 and (num - 1) % 6 != 0:
return False
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
return False
return True
c = 0
for i in range(n):
if isPrime(i):
c += 1
return c
埃氏筛选法
- 从2开始循环，已知2、3是最小的两个质数，然后将2的所有倍数都划去。然后是3，再将所有3的倍数都划去，
- 此时，4已经作为2的倍数被划掉了，到5，又是一个新的质数，再将所有5的倍数都划掉
算法优化
要判断一个质数，循环的话，最多循环到当前这个数的开放。因为后边的一定和前边有重合，比如2*5和5*2显然是一样的。
但是对于此算法，依然适用于本方法。不过关键点要变一下，不能再用进入判断c[i]==1的次数为结果了，比如0~9，7也是质数，但是7因为循环结束条件是sqrt(9)=3，7并不会进入循环。
因此，最后统计的话就应该统计1的个数，如果划掉条件为0，未划掉为1的话，也可以直接使用sum()。
代码
import math
class Solution:
def countPrimes(self, n: int) -> int:
if n < 3: # 题给条件，小于n，那么在此判断小于3，再小于2。即为1，0.因此直接返回0
return 0
c = [1 for i in range(n)] # 初始化质数列表
c[0], c[1] = 0, 0 # 已知0和1都不是质数，初始化
for i in range(2, int(math.sqrt(n)) + 1): # 开始循环
if c[i] == 1: # 如果当前这个数没被划掉(质数)
for j in range(i + i, n, i): # 划掉他所有的倍数，这里设置i为步长，减少循环个数，也不用再额外进行判断了
c[j] = 0
return sum(c) # 统计结果
