篩質數的三種方法時間複雜度及其實作：普通篩法，埃氏篩法，線性篩法

普通篩法 O(nlogn)

普通篩法做法是用每一個合數的所有因子篩去目前合數，比如24被2，3，4，6，8，12篩去6次

int get_primes(int n )
{
    for(int i = 2; i <= n ; i ++ )
    {
        if(!st[i])  //如果是質數
        {   primes[cnt ++] = i;
        }
        for(int j = i * 2 ; j <= n ; j += i)  st[j] = true;
        //不管目前i是合數還是質數，都用來篩掉後面它的倍數
    }
}
           

埃氏篩法 O(nloglogn)

埃氏篩法做法是隻用每一個合數的質因子篩去目前合數，比如24會被2，3篩去兩次

int get_primes(int n )
{
    for(int i = 2; i <= n ; i ++ )
    {
        if(!st[i])  //如果是質數
        {   primes[cnt ++] = i;
            for(int j = i * 2 ; j <= n ; j += i)  st[j] = true;  
            //隻用質數i篩掉它的倍數（合數），也可以篩掉所有合數
        }
    }
}
           

線性篩法 O(n)

線性篩法做法是隻用每一個合數的最小質因子篩去目前合數，比如24隻會被2篩去一次

int get_primes(int n )
{
    for(int i = 2 ; i <= n ; i ++ )
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0 ; primes[j] <= n / i ; j ++ ) 
//判斷條件解釋：我們用primes[j]篩掉合數primes[j] * i，隻用篩掉小于n的合數就可以了
        {
            st[primes[j] * i] = true;   
/*
每個合數隻會被自己的最小質因子篩，隻會被篩一次，是以O(n)
##如何證明目前primes[j]一定是primes[j] * i 的最小質因子？
因為當i % primes[j] != 0時,說明此時周遊到的primes[j]不是i的質因子
那麼隻可能是此時的primes[j] * i的最小質因子,
是以primes[j] * i的最小質因子就是primes[j];
就保證了用primes[j] * i的最小質因子篩去primes[j] * i
當 i % primes[j] == 0時,說明i的最小質因子是primes[j],是以primes[j] * i的最小質
因子也就應該是prime[j]，下一輪循環接着用st[primes[j+1] * i] = true去篩合數時，
就不是用最小質因子去更新了,因為i有最小質因子primes[j]，primes[j] < primes[j + 1]
此時的primes[j + 1]不是primes[j + 1] * i的最小質因子，
此時就應該退出循環，避免之後重複進行篩選。
*/
            if(i % primes[j] == 0) break;   
        }
    }
}