204. Count Primes

發表於 | 分類於

problem

solution

Sieve of Eratosthenes

option 1 - dp

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

analysis

  • time complexity O(nlogn)
  • space complexity O(n)