Python实现求质数的三种算法解析

Cora

发布时间：2026-10-13 | 2人浏览过

原创

本文详解Python中求小于n的质数个数的三种实现方式。从基础的穷举法，到利用平方根定理减少循环次数的优化法，再到基于已求质数列表进一步减少尝试次数的进阶法。重点解析第三种方法如何利用之前计算出的质数（如判断101时仅需尝试小于10的质数）来提升效率，帮助开发者理解不同算法的时间复杂度差异与适用场景。

本文整理了多种使用Python求质数的代码实现方案，供读者参考学习。

核心需求是统计所有小于给定数值n的质数总数。

第一种求解思路：

基础穷举法：依据质数定义，遍历判断该数是否能被大于1且小于其自身的自然数整除。若存在能整除的情况，则该数不是质数：

def countPrimes1(self, n):
  """
  :type n: int
  :rtype: int
  """
  if n<=2:
   return 0
  else:
   res=[]
  for i in range(2,n):
   flag=0 # 质数标志，=0表示质数
   for j in range(2,i):
    if i%j ==0:
     flag=1
   if flag==0:
    res.append(i)
  return len(res)

第二种求解思路：

基于数学定理优化：若一个数为合数，其最小质因数必然小于或等于该数的平方根。因此，判断质数时只需检查能否被小于其平方根的所有数整除。此方法可大幅减少运算量。

 def countPrimes2(self, n):
  if n<=2:
   return 0
  else:
   res=[]
  for i in range(2, n):
   flag=0
   for j in range(2, int(math.sqrt(i))+1):
    if i % j == 0:
     flag = 1
   if flag == 0:
    res.append(i)
  return len(res)

第三种求解思路：

延续上述定理，只需尝试小于等于平方根的所有数。进一步观察发现，若一个数不能被小质数（如3）整除，则必然不能被其倍数（如9）整除。因此，只需尝试小于平方根x的所有质数即可。这些质数已在之前的计算中生成并存储于列表res中。例如判断101是否为质数，101开根取整为10，需尝试1到10之间的数，但通过利用已存质数列表，可跳过非质数的尝试，直接验证其是否为质数。

 def countPrimes3(self, n):
  if n <= 2:
   return 0
  else:
   res = []
  for i in range(2, n):
   flag = 0
   for j in res:
    if i % j == 0:
     flag = 1
   if flag == 0:
    res.append(i)
  return len(res)

以上内容为本文全部分享，希望能为读者的学习提供助力，欢迎继续支持本站。