埃拉托色尼的筛子

在数学中，埃拉托色尼的筛子是一种古老的算法，用于寻找任何给定限度内的所有素数。它通过反复标记每个质数的倍数为复合数（即非质数），从xxx个质数2开始。一个给定的质数的倍数被生成为从该质数开始的数字序列，它们之间的恒定差值等于该质数。这是筛子与试除法的主要区别，试除法是按顺序测试每个候选数是否能被每个质数除尽。一旦每个被发现的质数的所有倍数都被标记为复合数，剩下的未标记的数字就是质数。

筛二和筛三：埃拉托色尼的筛子。当倍数升华时，剩下的数字就是质数。佚名一个质数是一个自然数，它正好有两个不同的自然数除数：数字1和它本身。用Eratosthenes的方法找到所有小于或等于给定整数n的素数。建立一个从2到n的连续整数的列表：（2，3，4，...，n）。首先，让p等于2，最小的素数。通过从2p到n的增量来列举p的倍数，并在列表中标记它们（这些将是2p，3p，4p，...；p本身不应该被标记）。找到列表中大于p的最小的数字，没有标记。如果没有这样的数字，就停止。否则，现在让p等于这个新的数字（这是下一个质数），然后从第3步开始重复。当算法终止时，列表中剩下的未标记的数字是低于n的所有质数。这里的主要想法是，给p的每个值都将是质数，因为如果它是复合的，它将被标记为一些其他更小的质数的倍数。请注意，有些数字可能会被标记不止一次。

作为一种改进，在步骤3中从p2开始标记数字就足够了，因为所有p的小倍数在这时已经被标记。这意味着，当p2大于n时，算法可以在第4步终止。另一个改进是最初只列出奇数，（3，5，...，n），并在第3步从p2开始以2p的增量计数，因此只标记p的奇数倍数，这实际上出现在原始算法中。这可以用轮子分解法来概括，只用与前几个质数共时的数字来形成初始列表，而不是只用几率（即与2共时的数字），并以相应的调整增量来计数，这样首先就只产生与这些小质数共时的p的倍数。