鱼C论坛

 找回密码
 立即注册

Sieve of Eratosthenes筛法找质数

已有 932 次阅读2013-8-16 17:48

很多算法的问题都涉及质数,所以有必要讨论一下关于质数的那些事
有以下事实
①.除了2以外所有的质数都是奇数
②.任何正整数N只能有一个大于根号N的质因子
③.任何小于正整数N的合数都有小于根号N的因子

Eratosthenes筛选法是用来寻找质数的算法,原理是这样的:比如求小于1000的质数,2是质数,去掉所有2的倍数,继续,3没有被去掉,所以3是质数,去掉3的倍数,直到根号1000。这样剩下来的数就都是质数了。

用python实现Sieve算法求解10000以内的质数,只用了0.1秒(我的计算机性能一般)
代码如下
应该还可以继续优化,等想到了再更新。

路过

鸡蛋

鲜花

握手

雷人

评论 (0 个评论)

facelist

您需要登录后才可以评论 登录 | 立即注册

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 06:17

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

返回顶部