筛法

欧拉筛法

void euler(int n, vector<int>& primes)
{
    primes.clear();
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        for (int p : primes) {
            if (1ll * i * p > n) break;
            isPrime[i * p] = false;
            if (i % p == 0) break;
        }
    }
}

埃拉托斯特尼筛法

void eratosthenes(int n, vector<int>& primes)
{
    primes.clear();
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) continue;
        primes.push_back(i);
        if (ll(i) * i > n) continue;
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
}