Leetcode/count_primes/Hash/리트코드

https://leetcode.com/problems/count-primes/submissions/

Count Primes - LeetCode

에라토스테네스의 체로 품 

Think of the array's index like the key in the Hash. Define the boolean array and let the index as the integer less than n, and let the value of the array have boolean value. 

int countPrimes(int n) {
    int answer = 0;
    vector<bool> isPrime(n+1, true);
    isPrime[1] = false;
    if (n == 1|| n==2){
        return answer = 0;
    }
    if(n==3){
        return answer = 1;
    }
    if (n==4) return answer = 2;
    
    for(int i = 2; i <= sqrt(n); i++){ // O(n^(3/2))
        if(isPrime[i]){
            for(int j = i+i; j < n; j+=i){
                isPrime[j]=false;
            }
        }
    }
    for(int i = 1; i < n; i++){
        if(isPrime[i]){
            answer++;
        }
    }
    return answer;
}