线性筛法求质数

思路：用最小质因数筛掉每个合数

• 遍历2到n的每一个数i,是质数就存下来
• 然后不管是不是质数都要进行下面的操作：

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

• 从小到大遍历每一个已经求得的质数primes[j]，直到primes[j]是i的因数为止（此时primes[j]也是i的最小质因数），容易证明这个过程中 primes[j] 始终是 primes[j]*i 的最小质因数

• 也就是说使得每个合数都被自己的最小质因数筛掉了
• 有一些证明细节可以自己去推导 结合算术基本定理

为什么是线型O(n)的?

大概是因为每个数都只会被筛一次

#include <iostream>
using namespace std;

const int NN = 1e6 + 10;
int n, cnt;
int st[NN], primes[NN];


int main(){
    cin >> n;
    for (int i = 2; i <= n; i ++){
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = 1;
            if (i % primes[j] == 0) break;
        }
    }
    cout << cnt << endl;

    return 0;
}