204 计数质数

[sailei1]

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

/**
 * @param {number} n
 * @return {number}
 */
// var countPrimes = function(n) {
//     //质数：只能被1和本身整除，1不是质数
//       let  res=1;//从3开始计算，所以初始为1 
//         if(n<3){ res=0;}
//         else{
//             for(let i=3;i<n;i++){
//                 if(i%2 == 0){
//                     continue;
//                 }
//                 let  flag=true;//false表示不是素数
//                 for(let j=3;j<=Math.sqrt(i);j+=2){
//                     if(i%j==0){
//                         flag=false;
//                         break;
//                     }
//                 }
//                 if(flag){res++; }
//             }
//         }
//         return res;
// };

var countPrimes = function(n) {
 if(n <= 2) {
        return 0
    }
    if(n === 3) {
        return 1
    }
    let count = 1;
    let arr = {};
    for(let i = 3; i < n; i += 2) {//叠加
        if(arr[i]) {
            continue;
        }
        count++;
        for(let j = i; j < n; j += i) { //叠加
            arr[j] = true; 
        }
    }
    return count;
};