试除法

时间复杂度：O($N\sqrt(N)$)

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
vector<int> primes;
for (int i = 2; i <= n; i++) {
    if (isPrime(i)) primes.push_back(i);
}

欧拉筛

时间复杂度：O($N$)

vector<int> eula(int n){
    vector<bool> is_prime(n+1, true);
    is_prime[0]=is_prime[1]=false;
    vector<int> primes;
    for(int i=2; i<=n; i++){
        if(is_prime[i]){
            primes.push_back(i);
        }
        for(int p: primes){
            if(i*p>n) break;
            is_prime[i*p]=false;
            if(i%p==0) break;
        }
    }
    return primes;
}
vector<int> ans = eula(n);