我们今天要介绍的埃拉托斯特尼算法就是他发明的用来筛选素数的方法,为了方便我们一般简称为埃式筛法或者筛法。埃式筛法的思路非常简单,就是用已经筛选出来的素数去过滤所有能够被它整除的数。这些素数就像是筛子一样去过滤自然数,最后被筛剩下的数自然就是不能被前面素数整除的数,根据素数的定义,这些剩下的数也是素数。

 

举个例子,比如我们要筛选出100以内的所有素数,我们知道2是最小的素数,我们先用2可以筛掉所有的偶数。然后往后遍历到3,3是被2筛剩下的第一个数,也是素数,我们再用3去筛除所有能被3整除的数。筛完之后我们继续往后遍历,第一个遇到的数是7,所以7也是素数,我们再重复以上的过程,直到遍历结束为止。结束的时候,我们就获得了100以内的所有素数。

 1 def eratosthenes(n):
 2     primes = []
 3     is_prime = [True] * (n + 1)
 4     for i in range(2, n+1):
 5         if is_prime[i]:
 6             primes.append(i)
 7             # 用当前素数i去筛掉所有能被它整除的数,i*2是因为第一次筛选过程会筛选所有2的倍数,从这个角度出发可能还有优化的空间
 8             for j in range(i * 2, n+1, i):
 9                 is_prime[j] = False
10     return primes

自己的代码:

#写的匆忙,明天验证优化下
def func(): nums=int(input()) primes = [] primes = [True]*(nums+1) for i in range(2,nums): if primes[i]: for n in range(2,nums+1): if i*n <= nums: primes[i*n]=False print(primes[2:]) if __name__=="__main__": func()

 

参考自:https://zhuanlan.zhihu.com/p/146418699

原文地址:http://www.cnblogs.com/mumuaa/p/16910151.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性