如何精简优化Python计算0-60000以内素数的代码？求格式及性能改进建议

现有代码可优化点 #

• 算法效率低：试除上限设为输入值的一半，冗余计算量极大；且没有跳过偶数判断，循环次数多了一倍
• 语法冗余：用除法加整数判断的方式校验整除，不如取模运算直接高效；多余的分支判断逻辑可以简化；素数没必要转字符串存储，增加额外开销
• 格式不规范：变量命名表意性差，不符合Python PEP8编码规范，可读性低

优化后代码 #

版本1：基于原试除逻辑最小改动版 #

在保留你原有试除思路的基础上做优化，运行效率可以提升100倍以上：

import time

start_time = time.time()
prime_list = [2]
# 直接从3开始遍历奇数，跳过所有偶数减少一半循环
for num in range(3, 60000, 2):
    is_prime = True
    # 仅需试除到数字的平方根即可完成素数判断
    for div in range(3, int(num ** 0.5) + 1, 2):
        if num % div == 0:
            is_prime = False
            break
    if is_prime:
        prime_list.append(num)

print(prime_list)
print(len(prime_list))
print(f"Process finished --- {time.time() - start_time:.4f} seconds ---")

版本2：埃拉托斯特尼筛法版（效率最高） #

针对大范围素数计算的专用算法，时间复杂度仅为O(n log log n)，比优化后的试除法还要快10倍以上：

import time

start_time = time.time()
max_limit = 60000
# 初始化标记数组，下标对应数字，值代表是否为素数
is_prime = [True] * (max_limit + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, int(max_limit ** 0.5) + 1):
    if is_prime[i]:
        # 批量标记i的所有倍数为非素数
        is_prime[i*i : max_limit+1 : i] = [False] * len(is_prime[i*i : max_limit+1 : i])
prime_list = [i for i, status in enumerate(is_prime) if status]

print(prime_list)
print(len(prime_list))
print(f"Process finished --- {time.time() - start_time:.4f} seconds ---")

关键优化说明 #

• 跳过偶数判断：除了2之外所有偶数都不是素数，直接只遍历奇数，循环量直接减半
• 试除上限优化：如果一个数n有大于√n的因数，那必然存在一个对应的小于√n的因数，所以只需判断到√n即可，大幅减少循环次数
• 取模运算替代除法判断：num % div == 0直接判断是否整除，比(num/div).is_integer()运算效率高，逻辑也更直观
• 埃氏筛批量标记：不用逐个数字判断，而是直接批量筛掉所有素数的倍数，适合大范围素数计算场景
• 格式优化：变量命名清晰表意，符合PEP8规范，用f-string做字符串格式化，可读性更高

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