算法创作|质数计数问题解决方法
问题描述
统计所有小于非负整数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 = 2 while j * j <= num: if num % j == 0: return False j += 1 return True count = 0 for i in range(2, n): if is_prime(i): count += 1 return count |
|---|
运行代码
结语
此类方法需要较为麻烦，思维较为复杂，需要单次判断每一个数是否为质数，淡然也可以采取枚举法、线性筛等方法，这些方法可能更容易理解，当我们遇到此类问题时，需迅速构建出各种方法，在这之中筛选，选出更简单的方法。
实习编辑：李欣容
作者：查萌雨 岳进 赵柔
稿件来源：深度学习与文旅应用实验室（DLETA）
腾讯云开发者
