這個是經典的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 閱讀(4667)
評論(5) 編輯 收藏 引用 所屬分類:
Algorithm - Number Theory