线性筛法

#include <iostream>
#include <vector>
using namespace std;

const int N = 5e7 + 10;
int primes[N], cnt;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; /* 1. j <= cnt && */ primes[j] <= n / i; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break; /* 2. 为什么要break掉 */
        }
    }
}

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

/*
0) 正确性
0.1) 一个合数一定会被最小质因子筛掉：在没有发生break之前，因为primes[j]是
     从小到大枚举的，所以primes[j]一定是primes[j] * i的最小质因子
0.2) 每个合数都会被筛掉：对于合数u，假设u的最小质因子是v，在i迭代到u之前会
     先迭代到u/v(因为u/v小于u，i是从小到大枚举的)，这个时候就会吧u筛掉
1) 为什么不需要j <= cnt? 
1.1) 当i是合数时，i的最小质因子k在primes数组内，所以在遍历完primes的元素之前
     会遍历到k，所以会提前break掉
1.2) 当i是质数时，i自己就会在primes数组内，所以在遍历完primes的元素之前会遍历
     到i，所以会提前break掉
2) 当在primes数组内找到i的最小质因子时，需要提前推出，否则下一次迭代的primes[j]
   就不是primes[j] * i的最小质因子了，就会出现重复筛掉的情况
*/

时间复杂度

O(n)

参考文献

https://www.acwing.com/video/293/
https://www.acwing.com/solution/content/31362/