204. Count Primes

This is a dynamic problem. The minimal prime is 2. So we can start from 2 and we know that any multiple of 2 is a prime. So we mark off all multiple of 2. Then we check 3. Similarly, and multiple of 3 is not a prime so we mark off them. Now we come to 4. Since 4 is a multiple of 2 and has been marked off, we just ignore and continue to 5. Note, we don't have to start from 5*2 because 5*2, 5*3, 5*4 have all been marked off before. So we can start from 5*5. Therefore, the algorithm is as following:

1:  class Solution {  
2:  public:  
3:    int countPrimes(int n) {  
4:      vector<bool> isPrime(n, true);  
5:      for (int i = 2; i*i < n; i++) {  
6:        if (!isPrime[i]) continue;  
7:        for (int j = i*i; j < n; j += i) {  
8:          isPrime[j] = false;  
9:        }  
10:      }  
11:      int count = 0;  
12:      for (int i = 2; i < n; i++) {  
13:        if (isPrime[i]) count++;  
14:      }  
15:      return count;  
16:    }  
17:  };