算法创作|质数计数问题解决方法

问题描述统计所有小于非负整数n的质数的数量。示例：输入：n = 10输出：4示例：输入：n = 1输出：0示例：输入：n = 0输出：0提示：0 <= n <= 5 * 106解决方案对于每个数 i，我们可以枚举 [2, i-1][2，i-1]区间的任意一个数 j，判断i 能否被j整除，枚举 [2, i-1][2,i−1] 区间的任意一个数j，判断i能否被j整除时，我们可以发现，如果i能够被j整除，那么这里的商也一定能够整除i，也就是i也能够被i/j整除。那么我们只要判断i和i/j其中一个能否整除i即可。代码清单 1统计所有小于非负整数n的质数的数量class Solution:def countPrimes(self, n: int) -> int:def is_prime(num):j = 2while j * j <= num:if num % j == 0:return Falsej += 1return Truecount = 0for i in range(2, n):if is_prime(i):count += 1return count运行代码

结语此类方法需要较为麻烦，思维较为复杂，需要单次判断每一个数是否为质数，淡然也可以采取枚举法、线性筛等方法，这些方法可能更容易理解，当我们遇到此类问题时，需迅速构建出各种方法，在这之中筛选，选出更简单的方法。实习编辑：李欣容作者：查萌雨 岳进 赵柔稿件来源：深度学习与文旅应用实验室（DLETA）