class Solution {
public:
    // 如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x… 一定不是质数
    int countPrimes(int n) {
        vector isPrime(n, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) 
        {
            if (isPrime[i]) 
            {
                ans += 1;
                if ((long long)i * i < n) 
                {
                    for (int j = i * i; j < n; j += i) 
                    {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
};