质数筛

试除法判断质数

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

这是一个经过优化的质数判断法，适用于单个质数判断，不适合大量判断质数的场景

质数筛专为重复大量判断质数的场景而生，常见的有埃式筛法，欧拉筛

埃式筛法

最经典，时间复杂度约为 O(n log log n)

vector<bool> getPrimes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; ++i) {
        if (!isPrime[i]) continue;
        for (int j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
    return isPrime;
}

欧拉筛

相比埃氏筛，不会重复标记合数，时间复杂度是线性的：O(n)

vector<int> getPrimes(int n) {
    vector<int> primes;
    vector<int> minPrime(n + 1, 0);

    for (int i = 2; i <= n; ++i) {
        if (minPrime[i] == 0) {
            minPrime[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > minPrime[i] || i * p > n) break;
            minPrime[i * p] = p;
        }
    }

    return primes;
}