在线学习
重点科目
初中数学
高中数学
高等数学
线性代数
概率统计
高中物理
数学公式
主要科目
复变函数
离散数学
数学分析
实变函数
群论
数论
未整理科目
近世代数
数值分析
常微分方程
偏微分方程
大学物理
射影几何
微分几何
泛函分析
拓扑学
数学物理
趣味数学
科数网
首页
教材
高考区
考研区
VIP
科数网
题库
在线学习
高中数学
高等数学
线性代数
概率统计
高中物理
复变函数
离散数学
你好
游客，
登录
注册
在线学习
数论
Eratosthenes筛法
最后
更新:
2023-10-24 14:14
查看:
252
次
反馈
刷题
Eratosthenes筛法
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$ ) 的质数。
开VIP会员
非会员每天6篇，会员每天16篇，VIP会员无限制访问
题库训练
自我测评
投稿
上一篇：
Pythagoras 方程
下一篇：
e的超越性
本文对您是否有用？
有用
(
0
)
无用
(
1
)
纠错
高考
考研
关于
赞助
公式
科数网是专业专业的数学网站。