筛质数
- 线性筛法 O(n)
- 埃氏筛法 O(nloglogn)

时间复杂度：O(n)

#include<iostream>
using namespace std;

const int N = 10010;
bool st[N];
int prime[N];
int cnt;
// 线性筛法筛质数
void get_prime1(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]){
            prime[cnt ++] = i;
        }
        for(int j = 0; prime[j] <= n / i; j ++){
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
// 埃氏筛法筛质数
void get_prime2(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]){
            prime[cnt ++] = i;
            for(int j = i + i; j <= n; j += i){
                st[j] = 1;
            }
        }
    }
}

int main(){
    int n;
    cin >> n;
    get_prime2(n);
    for(int i = 0; i < cnt; i ++)
        cout << prime[i] << " ";
    cout << endl;
    return 0;
}