RePorridge

Nothing change but our heart

时间复杂度O(n)筛素数(质数)

首先我们来了解一下素数(质数)的概念:一个数除了1和本身之外没有别的因数
除了素数之外的数就是合数:合数可以由多个素数相乘得如 A = p1^n1 * p2 ^ n3 * p3^n3 ……

我们预先把所有的大于等于2的数都标记为素数。
这样我们就可以想到先找到第一个素数2则,4,6,8,10……就都不是素数了。
下面是实现的方法。别人那里学来的。
--------------------------------------------------------------------------------------------
2016-5-11修改代码 for循环不能用<=越界访问
Onprime

posted on 2013-10-06 21:43 Porridge 阅读(500) 评论(0)  编辑 收藏 引用 所属分类: 日常笔记


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜