User:Corindo/埃拉托斯特尼筛法
埃拉托斯特尼筛法，简称埃氏筛，是一种用来寻找小于等于某个限定数值的所有素数，生成素数表的方法。它的思想是从2开始依次找出是其余数字若干倍的数（这些数都是合数）并删去，直到只剩下不是其余数若干倍的数，而这些数就是所有的素数。它得名于古希腊数学家、天文学家埃拉托斯特尼。埃拉托斯特尼关于筛法的作品文献已经佚失。最早提到埃拉托斯特尼的筛法的文字是古罗马数学家尼克马诸斯写于公元前一世纪的著作《数论导引》（Introduction to Arithmetic）。
方法 编辑
首先定义素数：素数是只能被1与它自身整除的自然数。埃拉托斯特尼筛法的目标是找出小于等于给定自然数N的所有素数。具体步骤是：
- 将从2到N的所有自然数排成一列：L = 2,3, ... ,N
- 找出L中没有被标记为素数也没有被划掉的数里面最小的一个：p（一开始来说，这个数是2），将p标记为素数。
- 将L中所有p的倍数（p自己除外）：2p、3p等等都划掉。
- 重复以上两步，直到L中所有的数都被标记或者被划掉。这时没被划掉的就是小于等于N的所有素数。
埃拉托斯特尼筛法的根据是：如果某个数p前面的数都被标记为素数或者被划掉了，而它还没被划掉，说明它不是2到p - 1中的任何数的倍数，即2到p - 1中没有一个数整除p。如果p是素数，那么在划掉2到p - 1的倍数时，p不会被划掉。所以当2到p - 1都被划掉以后，p成为了没被划掉的数里面最小的一个，从而它会被加入到素数表里去。合数必然会在划掉它的某个因子的所有倍数时被划掉，从而无法等到成为没被标记或没被划掉的数里面最小数的那个时刻。
为了提高效率，可以对埃拉托斯特尼筛法进行改良。注意到当我们开始划掉L中所有p的倍数时，我们实际上是从p2开始的。因为当k小于p时，kp也是k的倍数，所以在划掉k的倍数以后，kp肯定也被划掉了。所以筛法中划倍数的步骤可以改为：将L中所有p的倍数里大于等于p2的那些划掉。这也说明，当p2大于N时，筛法实际上就结束了，只需将剩余没有被划掉的数全部标记为素数即可。
无限定范围的筛法 编辑
埃拉托斯特尼筛法的目标是找出限定范围内的素数。稍作修改后，筛法可以用来生成素数序列，而不需要限定范围。
试除法 编辑
有时候，人们会将埃拉托斯特尼筛法与逐个试除法混淆起来。试除法是一种较为低效的寻找素数方法。给定限定范围N，试除法指对每个小于等于N的自然数n，用2到n-1来除n，验证n是否是素数。
例子 编辑
以下用埃拉托斯特尼筛法寻找小于等于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 3456789101112131415161718192021222324252627282930
比2大而还没被划掉的数里面最小的是3. 将3标记为素数，然后把所有3的倍数划掉：
2 3456789101112131415161718192021222324252627282930
比3大而还没被划掉的数里面最小的是5. 将5标记为素数，然后把所有5的倍数划掉：
2 3456789101112131415161718192021222324252627282930
比5大而还没被划掉的数里面最小的是7. 将7标记为素数，然后把7划掉，再把所有7的倍数划掉。然而这时候可以看到，所有7的倍数：(14, 21, 28)已经被划掉了。如果继续筛法，可以发现，之后的步骤都只有标记素数，而没有新的数被划掉了。最后剩下的数是：
2 3 5 7 11 13 17 19 23 29
如果使用改良的筛法，则步骤如下：
一开始把2标记为素数，然后从4开始把所有2的倍数划掉：
2 3456789101112131415161718192021222324252627282930
比2大而还没被划掉的数里面最小的是3. 将3标记为素数，然后从9开始，把所有3的倍数划掉：
2 3456789101112131415161718192021222324252627282930
比3大而还没被划掉的数里面最小的是5. 将5标记为素数，然后从25开始把所有5的倍数划掉：
2 3456789101112131415161718192021222324252627282930
比5大而还没被划掉的数里面最小的是7. 而7的平方已经大于30了。所以这时候可以停止筛法，这时剩余的数就是30以内所有的素数。
可以看到，两次筛法在任何时刻的状态都是一样的，但后者省去了重复划掉倍数的过程。