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 , '秒')