algo-aha

小于n的素数有几个

• https://leetcode.com/problems/count-primes/

int countPrimes(int n) {
    // 素数筛法
    vector<bool> prime(n, true);
    for (int i = 2; i * i < n; i++) {
        if (!prime[i]) continue;
        for (int j = i * i; j < n; j += i) {
            prime[j] = false;
        }
    }
    
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (prime[i]) count++;
    }
    return count;
}