(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 之后，只需要考虑标记较小因子的倍数。