python_习题练习_4_质数问题代码优化

# 需求：求100以内所有的质数

################################################

# 优化前：
#            10000个数，9.075549840927124 秒

# 第1次优化：
#             10000个数，1.059363842010498 秒
#             100000个数，82.62136554718018 秒

# 第2次优化：
#             10000个数，0.04787135124206543 秒
#             100000个数，1.0084514617919922 秒

################################################

# 优化前的代码：

# num= 2
# while num < 100 :
#     flag = True
#     i = 2
#     while i < num :
#         if num % i == 0 :
#             flag = False
#         i += 1 
#     if flag == True :
#         print(num)
#     num += 1

################################################

# 优化后的代码

from time import * # 引入time模块，计算代码运行时间

begin = time() # 记录代码开始执行前的时间

num= 2

while num < 10000 :
    flag = True
    i = 2
    # 第2次优化
    # 以36举例，因数有：
    # 1 36
    # 2 18
    # 3 12
    # 4 9
    # 6 6
    # num的平方根之后的循环判断和前面是对称的，没有执行的必要
    while i <= num ** 0.5 :
        if num % i == 0 :
            flag = False
            # 第1次优化
            # 一旦进入判断，则认为num一定不是质数，此时内层循环没有继续执行的必要
            # 使用break退出内层循环
            break
        i += 1 
    if flag == True :
        pass # 为了让if语句能够运行，加入pass
        # print(num) # print语句耗时太长，没有测试的必要，先注释掉
    num += 1

end = time() # 记录代码执行结束的时间

print('程序运行花费的时间是：', end - begin , '秒')