9
埃氏筛法求质数的互动演示
source link: https://www.lfhacks.com/t/sieve
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
埃氏筛法求质数的互动演示
埃拉托斯特尼筛法 是一种简单快速的求出质数集合的方法。从第一个质数2开始，将质数的倍数都剔除，从而得到新的质数。如此循环往复，就得到了质数的集合。本文试着以视图形式展示埃氏筛法。
下图是 埃拉托斯特尼筛法 的互动展示。使用方法： 从2开始，逐个点击数字。如果数字变灰或者消失，则不能点击。剩余的数字就是筛选出的质数。
使用方法： 从2开始，逐个点击数字。
表内仍然存在合数。
保留剔除的数 （最多显示1000） 23456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
停止筛选条件
有一个问题是，筛到多少我们就知道已经将一个集合内的所有质数全部筛选出来了？对于 埃氏筛法求质数 的筛选次数，有如下的定理：
对于一个原始集合，如果最近一次找出的质数，大于集合中最大数字的平方根，则表明所有质数已经找出。
比如，如果最大数是100，那么最多筛到10，就可以筛除100以内的全部质数。而实际上是当找到7时，就已经找出100以内的全部质数，因为8,9,10都已经在前面筛除。
坚持原创不易。如果您觉得有收获，请考虑资助本站，以期待更多原创文章。
打赏作者，支持小站
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK