204. 计数质数

 1 class Solution 
 2 {
 3 public:
 4     int countPrimes(int n) 
 5     {
 6         vector<bool> isPrime(n+1,true); //首先全部为true
 7         int count = 0;
 8 
 9         for(int i = 2; i < n;++i)//从2开始
10         {
11             if(isPrime[i])
12             {
13                 ++count;
14                 for(int j = 2 ; i * j < n ; ++j)//能被整除的全部筛掉，置为false
15                 {
16                     isPrime[i * j] = false;
17                 }
18             }
19         }
20         return count;
21     }
22     
23 };