老胡说科学 / 待分类 / 埃拉托色尼筛选法,找出所有小于给定正整...

分享

   

埃拉托色尼筛选法,找出所有小于给定正整数n的质数

2021-11-19  老胡说科学
在数学中,埃拉托色尼筛选法(the Sieve of Eratosthenes)是一种古老的算法,用来找出不超过任何给定整数n的所有质数。
它通过迭代地将每个质数的倍数标记为合数,从第一个质数2开始。一个给定质数的倍数组成一个以这个质数开头的等差数列,差就是这个质数。一旦所有发现的质数的倍数都被标记为合数,其余未标记的数就是质数。用埃拉托色尼筛法找到所有小于或等于给定整数n的质数:
  1. 建立一个从2到n的连续整数列表:(2, 3, 4, ……, n)。
  2. 最初,让p等于2,即最小的素数。
  3. 通过从2p到n的增量来列举p的倍数,并在列表中标记它们(这些将是2p,3p,4p,……;p本身不应该被标记)。
  4. 找出列表中大于p的最小的数字,该数字未被标记。如果没有这样的数字,就停止。否则,让p现在等于这个新的数字(这是下一个素数),然后从第3步开始重复。
当算法结束时,列表中剩下的未标记的数字是所有小于n的素数。

  • 121以下质数的算法步骤
这里的主要思想是,p的每一个值都是素数,因为如果它是合数,它将被标记为其他一些更小的素数的倍数。请注意,有些数字可能会被标记不止一次(例如,15将被标记为3和5)。
作为一种改进,在步骤3中从p^2开始标记数字就足够了,因为所有p的小倍数在这时已经被标记。这意味着,当p^2大于n时,算法可以在第4步终止。
举例
要找到所有小于或等于30的质数,按以下步骤进行。首先,生成一个从2到30的整数列表:
2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
列表中的第一个数字是2,从2开始以2为单位递增,划掉列表中2之后的第2个数字(这些将是列表中所有2的倍数):

2之后的数字是3,从3开始,划掉列表中3之后所有3的倍数的数字:
在3之后,下一个没有被划掉的数字是5,从5开始,划掉列表中5之后所有是5的倍数的数字:
下一个在5之后还没有划掉的数字是7,下一步是划掉7之后所有是7倍数的数字,但它们都已经划掉了,因为这些数字(14,21,28)也是较小质数的倍数,因为7 × 7大于30。此时,列表中未划掉的数字是所有低于30的质数:



    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>