筛法

说明

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

质数是大于 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 上的埃拉托斯特尼筛法