1.朴素算法：对于每个数，删掉他的倍数，最后留下来的就是质数。

• 时间复杂度：$O(nlogn)$

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) cnt ++;
        for (int j = i + i; j <= n; j += i) st[j] = true;
    }
}

2.埃氏筛法：把 $2$ ~ $p-1$ 当中的质数的倍数都筛掉即可

• 时间复杂度：$O(nloglogn)$
• 其实只是把计数放到符合条件的循环里，这样每次筛掉的都是质数的倍数

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            cnt ++;
            for (int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}

3. 线性筛法：n进会被最小质因子筛去

• 时间复杂度：$O(n)$, $n = 1e7$的时候基本就比埃式筛法快一倍了

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) prime[cnt ++] = i;

        // i枚举到n之前,一定会枚举到n/pj,当pj的i倍大于n时自然就会停止筛法.
        // 等价于primes[j] * i <= n，因为我们只需要筛选出n以内的质数，所以当乘积大于n的时候就可以停止了。
        for (int j = 0; prime[j] <= n / i; j ++) 
        {
            // pj 一定是 pj*i 的最小质因子
            // 1.如果i % prime[j] == 0，pj就是i的最小质因子
            // 2.如果 ！= 0，pj也一定小于i的最小质因子，所以pj也为pj*i最小质因子
            st[prime[j] * i] = true;

            if (i % prime[j] == 0) break;
        }
    }
}