【leetcode】204. 计数质数 暴力 & 埃拉托斯特尼法

示例:

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

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
  var count = 0;
  function isPrime(num){
    for(var i=2;i<=Math.sqrt(num);i++){
      if(num%i===0) return false
    }
    return true
  }
  for(var j=2;j<n;j++){
    if(isPrime(j)){
      count++
    }
  }
  return count
};

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
  var count = 0;
  var times = Array(n).fill(0);
  for(var i =2;i<times.length;i++){
    if(!times[i-1]){
      count++;
      for(var j=i*i;j<=n;j+=i){
        times[j-1]=true
      }
    }
    
  }
  return count
};