(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 的所有质数的倍数剔除，剩下的就是质数。

基本思路

埃氏筛的基本思路是：

1. 从2开始，依次标记每个素数的倍数为非素数。
2. 重复上述步骤，直到处理完所有小于等于√n的数。

具体步骤

1. 初始化：

   • 创建一个布尔列表 isPrimes，长度为 n，初始化为全 True。isPrimes[i] 表示数字 i 是否是素数。
   • 将 isPrimes[0] 和 isPrimes[1] 设为 False，因为0和1不是素数。

2. 标记非素数：

   • 从 2 开始遍历，每次找到一个未被标记为非素数的数字 i，将其所有倍数（从 i*i 开始）标记为非素数。
   • 之所以从 i*i 开始，是因为所有小于 i*i 的倍数在之前已经被处理过。

3. 优化：

   • 遍历的终止条件为 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 之后，只需要考虑标记较小因子的倍数。