科数网知识库
首页
目录
知识库
初等数论 Elementary Number Theory
初等数论
Eratosthenes筛法
Eratosthenes筛法
日期:
2023-10-24 14:14
查看:
16
次
更新
导出Word
Eratosthenes 筛法是一种用已知的质数寻找其他质数的方法。 ## 方法 若要找出不大于任意正整数 $N$ 的质数， - 首先，将不大于 $\sqrt{N}$ 的所有质数列出来。 - 然后将所有介于 $\sqrt{N}$ 和 $N$ 之间的所有(正)整数，以上一步骤中列出的质数试除，将其中可被除尽的数给删除，再将剩下的数以另一质数试除，之后一样将可除尽的数给删去，如此反复。剩下来的数即是不能被任何将不大于 $\sqrt{N}$ 的质数整除者，即为质数。 例若要找不大于 32 的质数，首先取 25 的平方根，也就是 $4 \sqrt{2}$ ，(正整数中)不大于 $4 \sqrt{2}$ 的质数有 $2 、 3 、 5$ 三个，然后列出 5 到 25 间的每个数，也就是以下几个数: $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 $ 然后先将这些数以 2 除一次，得以下数列: $5 、 7 、 9 、 11 、 13 、 15 、 17 、 19 、 21 、 23 、 25 、 27 、 29 、 31$ 注意6、8、10、12、14、16、18、20、22、24、26、28、30、32全都可被2给除尽，因此剩下的数都不可被2给除尽 然后再将剩下的数以3除一次，得以下数列: 5、7、11、13、17、19、23、25、29、31 注意9、15、21和27可被3给除尽，因此剩下的数不可被2或3给除尽。 然后再将剩下的数以 5 除一次，得以下数列: 5、7、11、13、17、19、23、29、31 25 在此被删去，剩下的数不可被2、3或 5 给除尽，它们都是不大于32的质数，用这些数可再去寻找所有不大于 1024( $1024=32^2$ ) 的质数。
上一篇：
Pythagoras 方程
下一篇：
没有了
知识库是科数网倾心打造的大型数学知识网站，欢迎各位老师、数学爱好者加入,联系微信 18155261033， 制作不易，也欢迎
赞助
本站。