问题描述
统计所有小于非负整数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）
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
