简介
你在旧货出售活动中买了一大箱杂乱的电脑零件,并开始组合它们,组装定制电脑。
为了比较不同零件组合的性能,你决定编写基准测试程序,选择了著名的埃拉托色尼筛法。它虽然古老,却足以检验计算机的运算能力。
任务说明
实现埃拉托色尼筛法,找出小于或等于给定数字的所有质数。
质数是大于 1,且只能被 1 和自身整除的整数,例如 2、3、5、7、11、13。6 不是质数,因为除了 1 和 6,还能被 2 和 3 整除。
先写下从 2 到给定数字的全部整数,然后执行:
- 找到下一个未标记的数字,跳过已标记数字。这个数字是质数。
- 把它的所有其他倍数标记为非质数。
重复直到遍历全部数字。最终未被标记的数字就是质数。
注意 筛法通过反复加上质数或直接乘法计算倍数来标记,而不是对每个数字逐一做整除测试。
测试只能检查质数结果是否正确,不能保证你的实现确实采用了筛法。
示例
寻找不超过 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] ↑
检查完后,2、3、5、7 仍未标记,它们就是不超过 10 的质数。