快速找出質數

如果要在一堆數字裡尋找質數，最基本的方式就是數字一個個的除以之前的數字，如果不能整除就是質數，但這種方式類似「窮舉法」( 全部可能的結果都拿出來找 )，在數字量大的時候會非常消耗電腦運算資源，所以這篇文章將會介紹使用「埃拉托斯特尼篩法」來快速找出質數。

本篇使用的 Python 版本為 3.7.12，所有範例可使用 Google Colab 實作，不用安裝任何軟體 ( 參考：使用 Google Colab )

埃拉托斯特尼篩法

埃拉托斯特尼篩法是古希臘數學家埃拉托斯特尼所發明，原理就是「依序將找到的質數的倍數剔除」，因此每次找到質數之後，要尋找的數字就會變少，所以可以快速找出質數。

詳細參考：埃拉托斯特尼篩法

快速找出質數

根據埃拉托斯特尼篩法，可以簡單撰寫出下方的程式碼，就能開始從 2～100 的數字之間尋找質數，但這種寫法雖然符合原則，但卻沒有效率 ( 每找一個質數就要寫一次 )。

參考：range、for 迴圈、串列生成式

a = range(2,100)                            # 產生 2～100 的串列
print(*a)
b = [i for i in a if i==a[0] or i%a[0]>0]   # 找出第一個質數，並將串列裡該質數的倍數剔除
print(*b)
c = [i for i in b if i==b[1] or i%b[1]>0]   # 找出第二個質數，並將串列裡該質數的倍數剔除
print(*c)
d = [i for i in c if i==c[2] or i%c[2]>0]   # 找出第三個質數，並將串列裡該質數的倍數剔除
print(*d)

觀察上方的程式碼，可以發現有許多重複的部分，因此可以使用「迴圈」的方式，將重複的部分獨立運作。

參考：區域變數、全域變數、函式

a = range(2, 100)        # 產生 2～100 的串列
p = 0                    # 設定 p 從 0 開始 ( 從 a[p] 也就是第一個項目開始 )
def g():                 # 定義一個函式 g
    global p, a            # 設定 p 和 a 是全域變數
    if p<len(a):           # 如果 p 小於 a 的長度 ( 依序取值到 a 的最後一個項目 )
        a = [i for i in a if i==a[p] or i%a[p]>0]  # 重新設定 a 為移除倍數後的串列
        p = p + 1            # p 增加 1
        g()                  # 重新執行函式 g
g()                      # 執行函式 g
print(*a)                # 印出 a ( 使用 * 將串列打散印出 )

使用 generator 函式

除了上述的方法，也可以使用 generator 函式來找出質數。

參考：產生器 generator、all、集合 set

def gg(max):                   # 定義一個 gg 函式
    s = set()                    # 設定一個空集合
    for n in range(2,max):       # 從 range(2, max) 當中開始依序找質數
        if all(n%i>0 for i in s):  # 判斷如果 i 已經存在於集合，且除以集合中的值會有餘數 ( 整除表示非質數 )
            s.add(n)                 # 將該數字加入集合 ( 表示質數 )
            yield n                  # 使用 yield 記錄狀態
print(*gg(100))                # 印出結果

意見回饋

如果有任何建議或問題，可傳送「意見表單」給我，謝謝～