素数筛法/Sieve out prime number

埃拉托斯特尼筛法(sieve of Eratosthenes)简称埃氏筛,是一种比较简单且也”相对”高效的素数筛法.
这个筛法的核心是通过遍历每个素数的倍数并将其标记为合数以获取最终的素数表.
step:
1.创建一个数组用来保存信息,先假设所有数字都是素数(except 1).
2.遍历2(首个素数)的所有倍数直到数组末尾,将这些数标记为合数.
3.在数组中找到下一个素数并重复第2步的操作,只到没有更大的素数为止.
当该算法结束时,数组中剩余的素数即是最终的素数表了.

Sieve of Eratosthenes,from Wikipedia
image from Wikipedia

code:

这个算法的复杂度大概是O(nlglgn),在大部分情况下效果也不差了.

 

欧拉筛法(Sieve of Euler)
//TODO

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据