埃拉托斯特尼筛法

埃拉托色尼的筛法是一种简单而古老的算法，用于寻找质数超过任何给定的限制。这是求小素数最有效的方法之一。

对于一个给定的上限 $n$该算法的工作原理是从2开始，迭代地将质数的倍数标记为合数。一旦2的所有倍数被标记为合数，下一个质数的倍数即3被标记为合数。这个过程一直持续到 $P \le \sqrt {n}$在哪里 $p$是一个质数。

筛工作

在下面的算法中，数字0表示合数。

1. 找出所有质数 $n$，生成一个从2到n的所有整数列表。请注意: 1不是质数)
2. 从最小素数开始 $p = 2$．
3. 标记所有的倍数 $p$小于 $n$复合。为此，标记数字的值(的倍数) $p$)在生成的列表中为0。不马克 $p$本身作为复合。
4. 赋值给 $p$敬下一个盛年。下一个素数是列表中大于p的下一个非零数。
5. 重复这个过程，直到 $P \le \sqrt {n}$．

我们是做!

现在所有非零数列中的数字表示质数，而数列中为0的数字表示合数。

示例1

生成所有小于11的质数

---

首先要注意的是不标记质数自己是合成的。

1. 创建一个从2到10的整数列表。List = [2,3,4,5,6,7,8,9,10]
2. 开始 $p = 2$．
3. 自 $2 ^ 2 \ le 10$,继续。
4. 通过在列表中将2的所有倍数设置为0，将其标记为合数。List = [2,3, 0,5, 0,7, 0,9, 0]
5. 赋值给 $p$到下一个质数，即3。
6. 自 $3 ^ 2 \ le 10$,继续。
7. 通过在列表中将3的所有倍数设置为0，将其标记为合数。List = [2,3, 0,5, 0,7, 0,0,0]
8. 赋值给 $p$5。
9. 自 $n . n$,停止。

我们是做!

列表[2,3, 0, 5, 0, 7, 0, 0, 0]．因为所有0的数都是合数，所以所有非0的数都是素数。因此小于11的质数是2 3 5 7。 $_ \广场$

示例2

生成小于任何整数的所有质数 $n$

---

自 $n$可能是任何一个大数字，手动计算出答案需要数年时间。让我们为此写一个代码。

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

进口数学n＝200# n是任意整数列表＝［］为x在xrange（2，n)：#添加从2到n - 1的数字到列表列表．附加（x）#注意上面的语句等价于List = range(2, n)p＝2# p是质数而不int（数学．√6（p）)+1>n：#继续标记质数，直到平方根p小于n为x在xrange（p＊2，n，p)：#删除所有p的倍数列表［x-2］＝0p+ =1而p-2<len（列表）而且列表［p-2］= =0：#将p赋给下一个质数。下一个质数是数列中的下一个非零数p+ =1为x在列表：#搜索列表中的非零或质数并打印它们如果x! =0：打印x

---

这是一个优化的java版本-

12 34 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 31 32 33 34 35 36 37

最后intlim＝200；/ /独家intn［］＝新int［lim-2］；/ /排除1为（int我＝2；我< =lim-1；我++）//用从2到lim的整数初始化数组｛如果（(我＆1）= =0）//偶数不是质数f & 1如果f % 2 == 0返回0｛n［我-2］＝0；｝其他的｛n［我-2］＝我；｝｝n［0］＝2；intp＝3.；//以质数开头。既然2已经被消去了，就从3开始而（p＊p<lim）｛为（int我＝p＊p；我<lim；我+ =p+p）//删除质数的倍数。从p * p开始｛n［我-2］＝0；｝而（n［（p+ =2）-2］= =0）//查找下一个非零数字。这肯定是质数。；｝为（int我＝0；我<lim-2；我++）//打印非零数字｛如果（n［我］! =0）｛系统．出．println（n［我］）;｝｝

证明:来看看为什么埃拉托色尼的筛子会产生所有的质数

为了首先理解筛子的工作原理，让我们看看质数分解和合数的定义。

---

定理1

每一个整数大于1可以表示为质数的乘积。

---

定理2

如果任何整数 $n$是复合,那么 $n$质因数是否小于或等于 $\sqrt {n}$．

---

因为对于任何数字 $n$在列表中，我们寻找所有的质数，直到 $\sqrt {n}$，我们实际上是在分离所有的合数。因此埃拉托色尼筛法产生的质数都小于上限值。 $_ \广场$