这个是经典的Eraosthenes筛法：
for (int i = 2; i * i < N; i++)
{
if (tag[i]) continue;
for (int j = i; i * j < N; j++)
tag[i*j] = 1;
}
for (int i = 2; i < N; i++)
if (!tag[i])
prime[tol++] = i;
但是Eraosthenes筛法的速度并不快，原因在于对于一个合数，这种方法会重复的标记。一种线性筛素数的方法有效的解决了这一点，代码如下：
void get_prime()
{
int cnt = 0;
for (int i = 2; i < N; i++)
{
if (!tag[i]) p[cnt++] = i;
for (int j = 0; j < cnt && p[j] * i < N; j++)
{
tag[i*p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
}
可以用均摊分析的方法来分析这个算法的复杂度：由于每个合数都唯一的被它的最小素因子筛一次，而每个合数的最小素因子都是唯一的，因此总复杂度是O(n)。
这种筛法的思想很强悍，有很多利用价值，可以根据这种方法做到线性筛欧拉函数等等，继续研究中。。
posted on 2009-03-16 21:29
sdfond 阅读(4616)
评论(5) 编辑 收藏 引用 所属分类:
Algorithm - Number Theory