(day18) leetcode 204.计数质数
描述
给定整数 n
,返回 所有小于非负整数 n
的质数的数量 。
示例 1:
输入:n = 10 输出:4 解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:
输入:n = 0 输出:0
示例 3:
输入:n = 1 输出:0
提示:
0 <= n <= 5 *
超时代码
class Solution:def countPrimes(self, n: int) -> int:num=0for i in range(2,n):for j in range(2,int(math.sqrt(i))+1):if i%j == 0:breakelse:num+=1return num
优化后的埃氏筛(
来自Leecod题解powcai)
class Solution: def countPrimes(self, n: int) -> int: # 定义一个函数 countPrimes,接受一个整数 n 作为参数,并返回一个整数if n < 2: # 如果 n 小于 2,直接返回 0,因为 2 是最小的素数,n 小于 2 不会有素数return 0 # 创建一个长度为 n 的列表 isPrimes,初始化为全 1,表示所有数都是潜在的素数isPrimes = [1] * n # 将索引 0 和 1 对应的位置设为 0,因为 0 和 1 不是素数isPrimes[0] = isPrimes[1] = 0 # 遍历从 2 到 sqrt(n) 的整数(包含 sqrt(n)),这是埃拉托色尼筛法的优化步骤for i in range(2, int(math.sqrt(n)) + 1): if isPrimes[i] == 1: # 如果 i 是素数(即 isPrimes[i] 为 1)# 将 i 的所有倍数(从 i*i 开始,到 n 结束,步长为 i)标记为非素数(设为 0)isPrimes[i * i:n:i] = [0] * len(isPrimes[i * i:n:i]) # 返回 isPrimes 列表中所有素数的个数(即值为 1 的元素的个数)return sum(isPrimes)
效率提升的关键在于埃拉托斯特尼筛法,简称埃式筛,也叫厄拉多塞筛法:
要得到自然数 n 以内的全部质数,必须把不大于 根号n 的所有质数的倍数剔除,剩下的就是质数。
基本思路
埃氏筛的基本思路是:
- 从2开始,依次标记每个素数的倍数为非素数。
- 重复上述步骤,直到处理完所有小于等于√n的数。
具体步骤
-
初始化:
- 创建一个布尔列表
isPrimes
,长度为n
,初始化为全True
。isPrimes[i]
表示数字i
是否是素数。 - 将
isPrimes[0]
和isPrimes[1]
设为False
,因为0和1不是素数。
- 创建一个布尔列表
-
标记非素数:
- 从
2
开始遍历,每次找到一个未被标记为非素数的数字i
,将其所有倍数(从i*i
开始)标记为非素数。 - 之所以从
i*i
开始,是因为所有小于i*i
的倍数在之前已经被处理过。
- 从
-
优化:
- 遍历的终止条件为
i <= √n
,因为如果i > √n
,则i
的所有倍数都已经在之前被标记。
- 遍历的终止条件为
优化思路的详细解释
为什么从 i*i
开始标记?
当你处理到某个数 i
时,所有比 i*i
小的 i
的倍数都已经在之前的步骤中被标记。例如,当处理 i = 3
时,3 的倍数 6
、9
等已经在处理 i = 2
时被标记了。因此,从 i*i
开始标记可以避免重复操作,提高效率。
为什么只需处理到 √n
?
对于一个合数 n
,它必然可以表示为两个整数的乘积,即 n = a * b
。如果 a
和 b
都大于 √n
,则 a * b > n
,这不可能。因此,在 √n
之后,只需要考虑标记较小因子的倍数。