埃氏筛法求质数

发表时间

埃拉托斯特尼筛法 是一种简单快速的求出质数集合的方法。从第一个质数2开始,将质数的倍数都剔除,从而得到新的质数。如此循环往复,就得到了质数的集合。本文试着以视图形式展示埃氏筛法。

互动展示

下图是 埃拉托斯特尼筛法 的互动展示。使用方法: 从2开始,逐个点击数字。如果数字变灰或者消失,则不能点击。剩余的数字就是筛选出的质数。

筛选次数

对于一个原始集合,如果最近一次找出的质数,大于集合中最大数字的平方根,则表明所有质数已经找出。

比如,如果最大数是121,那么当找到11时,就已经找出全部质数,大于11的全部合数已经全部筛除。这时再点击大于11的数字,比如13,已经不能再筛选出更多的合数。


  欢迎到 留言板 写下你的看法。
  本页面内容采用 署名协议 CC-BY 授权。欢迎转载,请保留原文链接