# \#204 Count Primes
## *計算<n的質數個數*
## Log
- build 20210425 by syhuang

## 質數篩選法(厄拉托西尼篩法)
- 從2開始, 將2的n倍皆紀錄為不是質數(都可以被2整除), 往下迴圈, 已經記錄過的就跳過, 最後就可以獲得<n的所有質數個數

var countPrimes = function(n) {
    if(n < 2) return 0;
    var notPrime = new Array(n);
    var result = 0;
    for(var i=2; i<n; i++){
        if(!notPrime[i]){
            result++;
            for(var j=2; i*j<n; j++){
                notPrime[i*j] = true;
            }
        }
    }
    return result;
};

## 初見(超過時限)
- 從3開始跑迴圈檢查每個數是否為質數(可以被因數分解的就不是質數,檢查其是否可以被<n/2 的數整除)
- 暴力解法超過時間限制
## 備註
## 參考
- [參考解答](https://leetcode.com/problems/count-primes/discuss/57588/My-simple-Java-solution)
- [質數篩](https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)
###### tags: `leetcode`, `leetcode-easy`