埃氏筛法求质数的互动演示

2019-06-19

互动展示

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

停止筛选条件

有一个问题是,筛到多少我们就知道已经将一个集合内的所有质数全部筛选出来了?对于 埃氏筛法求质数埃氏筛法求质数的筛选次数,有如下的定理:

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

比如,如果最大数是100,那么最多筛到10,就可以筛除100以内的全部质数。而实际上是当找到7时,就已经找出100以内的全部质数,因为8,9,10都已经在前面筛除。

捐助本站

为了保证阅读体验,本站不安放广告。但是,租用服务器和编写文章需要个人资金和时间的投入。

如果您觉得文章对您有用,请考虑捐助小站(金额不限),以期待更多原创文章。捐助记录

本站是个人网站,若无特别说明,文章均为原创,并采用 署名协议 CC-BY-NC 授权。
欢迎转载,惟请保留原文链接,且不得用于商业用途。

相关文章