埃拉托斯特尼筛法

实践练习C++17

简介

你在旧货出售活动中买了一大箱杂乱的电脑零件,并开始组合它们,组装定制电脑。

为了比较不同零件组合的性能,你决定编写基准测试程序,选择了著名的埃拉托色尼筛法。它虽然古老,却足以检验计算机的运算能力。

任务说明

实现埃拉托色尼筛法,找出小于或等于给定数字的所有质数。

质数是大于 1,且只能被 1 和自身整除的整数,例如 2、3、5、7、11、13。6 不是质数,因为除了 1 和 6,还能被 2 和 3 整除。

先写下从 2 到给定数字的全部整数,然后执行:

  1. 找到下一个未标记的数字,跳过已标记数字。这个数字是质数。
  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 的质数。