朴素筛 $O(n \log n)$

用n以内每个数的倍数来筛

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

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

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

埃氏筛 $O(n \log \log n)$

用n以内每个质数的倍数来筛

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

int get_primes(int n)
{
    // 遍历到p，如果p没被筛掉，那p就是质数，就筛掉n以内p的所有倍数
    for (int p = 2; p <= n; p ++) {
        if (st[p]) continue;
        primes[cnt ++] = p;
        for (int x = p << 1; x <= n; x += p)
            st[x] = true;
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}

线性筛 $O(n)$

用每个数的最小质因子来筛

1、证明 primes[i] 是 primes[i] * x 的最小质因子

分类讨论

1. 当 x % primes[i] == 0 时

   primes[i] 一定是x的最小质因子
   因此，primes[i] 一定是 x * primes[i] 的最小质因子

2. 当 x % primes[i] != 0 时

   primes[i] 一定小于x的所有质因子
   因此，primes[i] 一定是 x * primes[i] 的最小质因子

因此无论如何，primes[i] 一定是 x * primes[i] 的最小质因子

2、证明最小质因子能够筛掉所有合数

任何一个合数 c 都存在最小质因子，假设 primes[i] 是 c 的最小质因子
在 x 枚举到 c 之前一定会枚举到 c / primes[i]
当枚举到 c / primes[i] 时，c 就会被筛掉
因此每个合数 c 在被枚举到之前一定会被筛掉

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

int get_primes(int n)
{
    for (int x = 2; x <= n; x ++)
    {
        if (!st[x]) primes[cnt ++] = x;

        for (int i = 0; primes[i] <= n / x; i ++)
        {
            st[primes[i] * x] = true;       
            if (x % primes[i] == 0) break;  
        }
    }
}

int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}