筛质数的三种方法时间复杂度及其实现：普通筛法，埃氏筛法，线性筛法

普通筛法 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;   
        }
    }
}