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

筛法

简单

简介

你在旧货市场上买了一大箱乱七八糟的电脑零件，然后开始把这些零件拼装起来，自己组装电脑。

你想测试不同零件组合的性能，于是决定写一个自己的基准测试程序，看看这些电脑表现如何。你选中了著名的“埃拉托斯特尼筛法”算法。这是一个古老的算法，却能把你电脑的性能压到极限。

说明

你的任务是编写一个程序，实现埃拉托斯特尼筛法，找出所有小于或等于给定数字的质数。

质数是大于 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]
                         ↑
```