Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

篩法

簡單

簡介

你在車庫拍賣上買了一大箱隨機的電腦零件。你開始把這些零件組裝起來，打造自訂的電腦。

你想測試各種零件組合的效能，於是決定自己寫一個效能測試程式，看看你的電腦表現如何。你選擇了著名的「Sieve of Eratosthenes」演算法，這是個古老的演算法，但應該能讓你的電腦效能發揮到極限。

說明

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

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

要使用埃拉托斯特尼篩法，首先把從 2 到給定數字（含）的所有數字都寫出來。接著，依照下列步驟：

重複這些步驟，直到檢查過每一個數字。最後，所有沒有被標記的數字都是質數。

Note

埃拉托斯特尼篩法是用加法（反覆加上該質數）或乘法（直接計算它的倍數）來劃掉每個質數的倍數，而不是逐一檢查每個數字能不能被整除。

測試不會檢查你是否實作了這個演算法，只會檢查你算出的質數是否正確。

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

寫出 2、3、4、5、6、7、8、9、10，全部先不標記。
```
2 3 4 5 6 7 8 9 10
```
2 沒有被標記，所以是質數。把 4、6、8 和 10 標記為「非質數」。
```
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
```
3 沒有被標記，所以是質數。把 6 和 9 標記為非質數_（標記 6 是選擇性的，因為它已經被標記過了）_。
```
2 3 [4] 5 [6] 7 [8] [9] [10]
  ↑
```
4 已被標記為「非質數」，所以我們跳過它。
```
2 3 [4] 5 [6] 7 [8] [9] [10]
     ↑
```
5 沒有被標記，所以是質數。把 10 標記為非質數_（選擇性的，因為它已經被標記過了）_。
```
2 3 [4] 5 [6] 7 [8] [9] [10]
        ↑
```
6 已被標記為「非質數」，所以我們跳過它。
```
2 3 [4] 5 [6] 7 [8] [9] [10]
           ↑
```

7 沒有被標記，所以是質數。

2 3 [4] 5 [6] 7 [8] [9] [10]
              ↑

8 已被標記為「非質數」，所以我們跳過它。
```
2 3 [4] 5 [6] 7 [8] [9] [10]
                 ↑
```
9 已被標記為「非質數」，所以我們跳過它。
```
2 3 [4] 5 [6] 7 [8] [9] [10]
                     ↑
```
10 已被標記為「非質數」，所以我們停下來，因為已經沒有其他數字要檢查了。
```
2 3 [4] 5 [6] 7 [8] [9] [10]
                         ↑
```