导航：首页 > 开发技术 >

如何解决质数计数问题

发表于：2025-01-30 作者：千家信息网编辑

千家信息网最后更新 2025年01月30日，这篇文章主要介绍"如何解决质数计数问题"，在日常操作中，相信很多人在如何解决质数计数问题问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"如何解决质数计数问题"的疑惑有所帮

千家信息网最后更新 2025年01月30日如何解决质数计数问题

这篇文章主要介绍"如何解决质数计数问题"，在日常操作中，相信很多人在如何解决质数计数问题问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"如何解决质数计数问题"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

问题描述

统计所有小于非负整数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):