篩法

說明

你的任務是寫一個程式，實作埃拉托斯特尼篩法，找出小於或等於指定數字的所有質數。

質數是大於 1、而且只能被 1 和自己整除的數字。例如 2、3、5、7、11 和 13 都是質數。相對地，6 就_不是_質數，因為它除了能被 1 和自己整除外，還能被 2 和 3 整除。

使用埃拉托斯特尼篩法時，你要先建立一份清單，列出 2 到指定數字之間的所有數字。接著反覆進行以下步驟：

1. 找出清單中下一個還沒被標記的數字（跳過已標記的數字）。這個數字就是質數。
2. 把這個質數的所有倍數標記為非質數。

不斷重複這些步驟，直到清單中的每個數字都處理過為止。最後，所有沒有被標記的數字都是質數。

範例

假設你要找出小於或等於 10 的質數。

• 列出 2、3、4、5、6、7、8、9、10，全部都先不標記。
• 2 沒有被標記，所以它是質數。 把 4、6、8 和 10 標記為「非質數」。
• 3 沒有被標記，所以它是質數。 把 6 和 9 標記為非質數_（標記 6 是可選的，因為它已經被標記過了）_。
• 4 已被標記為「非質數」，所以跳過。
• 5 沒有被標記，所以它是質數。 把 10 標記為非質數_（可選，因為它已經被標記過了）_。
• 6 已被標記為「非質數」，所以跳過。
• 7 沒有被標記，所以它是質數。
• 8 已被標記為「非質數」，所以跳過。
• 9 已被標記為「非質數」，所以跳過。
• 10 已被標記為「非質數」，所以停下來，因為已經沒有數字要檢查了。

你已經檢查過所有數字，發現 2、3、5 和 7 仍然沒有被標記，這表示它們就是小於或等於 10 的質數。

---

出處

Wikipedia 上的埃拉托斯特尼篩法。