47.算法->获取n以内所有素数个数

day1：假期打卡失败，节后继续刷题
算法->计数质数

• 素数->质数；大于1的自然数，除了1和他本身以外不再有其他因数的自然数
• 因数：整数a除以整数b的商正好是整数而没有余数，就说b是a的因数
• 相当于双重for循环，外层for循环做统计，内层for循环用来判断是否质数用来做判断
• 注意：不能使用双重for循环来实现，需要根据for循环的结果(j * j <= i)来判定是否进行ans++操作

问题：计算结果正确，会出现提交超时的情况

//判断是否是质数
function isPrime(x) {
  for (let i = 2; i * i <= x; ++i) {
    if (x % i === 0) {
      return false;
    }
  }
  return true;
}
//统计质数个数
function countPrimes(n) {
  if (n < 1) return 0;
  let ans = 0;
  for (let i = 2; i < n; ++i) {
    if (isPrime(i)) {
      ans++;
      // console.log("ans", ans);
    }
    // for (let j = 2; j * j <= i; ++j) {
    //   if (i % j !== 0) {
    //     ans++;
    //   }
    // }
  }
  return ans;
}

console.log(countPrimes(348436));