快速找出质数

如果要在一堆数字里寻找质数，最基本的方式就是数字一个个的除以之前的数字，如果不能整除就是质数，但这种方式类似“穷举法”( 全部可能的结果都拿出来找 )，在数字量大的时候会非常消耗电脑运算资源，所以这篇文章将会介绍使用“埃拉托斯特尼筛法”来快速找出质数。

本篇使用的 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))                # 印出結果

意见反馈