線性篩法（歐拉篩法）求素數，歐拉素數

線性篩法（歐拉篩法）求素數，歐拉素數

時間復雜度O(n)當n比較大時歐拉篩法所用的時間比O(nloglogn)的算法的時間少的會越來越明顯

為什麼呢?

因為在歐拉篩法中，每一個合數只被訪問並將其所對的f[]的值修改了一次。

for(i = 2; i <= n; i++)
{
    if(f[i] == 0)
    {
        p[++cnt] = i;
    }
    for(j = 1; j <= cnt; j++)
    {
        if(i * p[j] > n)break;
        f[i * p[j]] = 1;
        if(i % p[j] == 0)break;
    }
}