這個(gè)是經(jīng)典的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篩法的速度并不快，原因在于對(duì)于一個(gè)合數(shù)，這種方法會(huì)重復(fù)的標(biāo)記。一種線性篩素?cái)?shù)的方法有效的解決了這一點(diǎn)，代碼如下：
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;
}
}
}
可以用均攤分析的方法來分析這個(gè)算法的復(fù)雜度：由于每個(gè)合數(shù)都唯一的被它的最小素因子篩一次，而每個(gè)合數(shù)的最小素因子都是唯一的，因此總復(fù)雜度是O(n)。
這種篩法的思想很強(qiáng)悍，有很多利用價(jià)值，可以根據(jù)這種方法做到線性篩歐拉函數(shù)等等，繼續(xù)研究中。。