(Leet Code c++)Count Primes

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 answer = 0;
        vector<bool> prime(5000001, false);
        
        for(int i = 2; i < n; i++){
            if(!prime[i]){
                answer++;
                for(int j = i + i; j < n; j += i){
                    prime[j] = true;
                }
            }
        }
        
        return answer;
    }
};