质数筛

//埃氏筛
std::vector<int> eratosthenesSieve(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    if (n < 2) return primes;

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            // 从 i * i 开始标记，避免重复标记小于 i^2 的倍数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}