Python质数密度计算：区间质数统计代码技术咨询

嘿，我来帮你搞定这个质数统计代码的验证和优化问题～ 先从正确性验证说起，再给你唠几个能显著提升效率的实用思路。

一、如何验证代码正确性？ #

咱可以从这几个角度去测试，确保代码统计的质数数量是准确的：

• 边界值测试：
  • 测试区间[2,2]，应该返回1（2是最小的质数）；
  • 测试区间[0,1]，应该返回0（没有质数）；
  • 测试题目示例中的[0,100]，结果必须是25，和给出的参考值一致。
• 小范围手动核对：
  比如区间[2,10]，质数是2、3、5、7，共4个，跑代码看看输出的总数是不是4。
• 对比可靠实现：
  写一个极简的参考版本（用Python内置的math.isqrt做快速判断），和原代码对比结果，比如：

  import math
  
  def is_prime(n):
      if n <= 1:
          return False
      if n == 2:
          return True
      if n % 2 == 0:
          return False
      for i in range(3, math.isqrt(n)+1, 2):
          if n % i == 0:
              return False
      return True
  
  # 用这个函数统计区间质数数量，和原代码结果对比
  lower = 0
  upper = 100
  count = sum(1 for num in range(lower, upper+1) if is_prime(num))
  print(count)  # 应该输出25
  

二、效率优化的几个实用方向 #

原代码的内层循环要遍历到num-1，效率很低，尤其是当upper很大的时候，咱可以从这几个点优化：

1. 缩小内层循环的上限到平方根 #

一个数如果有因数，那必然有一个因数小于等于它的平方根。所以内层循环不用跑到num，只需要跑到sqrt(num)就行，用math.isqrt（Python3.8+）能避免浮点运算的误差：

import math

lower = int(input("Enter lower range: "))
upper = int(input("Enter upper range: "))
total = 0
print("Prime numbers between", lower, "and", upper, "are:")

for num in range(lower, upper + 1):
    if num > 1:
        # 循环到num的平方根+1即可
        for i in range(2, math.isqrt(num) + 1):
            if (num % i) == 0:
                break
        else:
            total += 1
print("Total primes:", total)

2. 提前排除偶数，减少循环次数 #

除了2之外，所有偶数都不是质数，所以我们可以单独处理2，然后只遍历奇数，直接减少一半的循环量：

import math

lower = int(input("Enter lower range: "))
upper = int(input("Enter upper range: "))
total = 0

# 先处理2的情况
if lower <= 2 <= upper:
    total += 1
    print(2, end=" ")

# 遍历奇数，步长设为2
start = max(lower, 3) if lower % 2 == 0 else max(lower, 3)
for num in range(start, upper + 1, 2):
    is_p = True
    for i in range(3, math.isqrt(num) + 1, 2):  # 只检查奇数因数
        if num % i == 0:
            is_p = False
            break
    if is_p:
        total += 1
        print(num, end=" ")

print("\nTotal primes:", total)

3. 埃拉托斯特尼筛法（适合大区间场景） #

如果你的区间范围很大（比如upper是10^6甚至更大），逐个判断每个数是不是质数的效率就不够了，这时候用埃拉托斯特尼筛法会快很多——先筛出所有小于等于upper的质数，再统计区间内的数量：

import math

def sieve(upper):
    if upper < 2:
        return []
    # 初始化筛子，默认所有数都是质数
    is_prime = [True] * (upper + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, math.isqrt(upper) + 1):
        if is_prime[i]:
            # 标记i的倍数为非质数，从i²开始更高效
            for multiple in range(i*i, upper+1, i):
                is_prime[multiple] = False
    # 返回所有质数
    return [num for num, prime in enumerate(is_prime) if prime]

lower = int(input("Enter lower range: "))
upper = int(input("Enter upper range: "))
primes = sieve(upper)
# 统计区间内的质数数量
total = sum(1 for p in primes if lower <= p <= upper)
print("Prime numbers between", lower, "and", upper, "are:", primes)
print("Total primes:", total)

这个方法的时间复杂度是O(n log log n)，比逐个判断的O(n√n)高效太多，适合大区间场景。

内容的提问来源于stack exchange，提问作者Yer Maw