[leetcode 204] Count Primes

Count the number of prime numbers less than a non-negative number, n.

 

Example 1:

Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0 Output: 0

Example 3:

Input: n = 1 Output: 0

 

Constraints:

• 0 <= n <= 5 * 106

문제 풀이:

에라토스테네스의 체를 사용

class Solution {
public:
    int countPrimes(int n) {
       
        int result = 0;
        if(n<=2){return result;}
        
        vector<int> v(n,0);
        
        for(int i=2; i<n; i++){
            
            if(v[i] == 0){
                result++;
                
                for(int j = i; j<n; j += i){
                    v[j] = 1;
                }
            }
            
        }
        return result;
    }
};