埃氏筛

#include <iostream>
using namespace std;
class Solution{
public:
    int CountPrime(int n){
        vector<int>isPrime(n,1);
        int count=0;
        for(int i=2;i<n;i++)
        {
            if(isPrime[i])
            {
                count++;
                if(long long i*i<n)
                {
                    for(int j=i*i;j<n;j+=i)
                        isPrime[j]=0;//质数的倍数肯定不是质数了
                }
            }
        }return count;
    }
}