内容
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
思路
这道题的关键点就在于如何更有效的判断一个数为质数
那么这里举几个例子
比如16，那么有1*16，2*8，4*4，8*2，16*1这几个整数相乘的结果等于16。
再来看一个，
25，1*25，5*5，25*1
20，1*20，2*10，4*5，5*4，10*2，20*1
那么这里可以发现有如下规律：
众多 i*j=n 中，总有一个小于并最接近sqrt(n)开根号的整数k，
使得以后的所有i*j开始变成j*i，也就是说，从k以后，
下一个i*j就会开始和前面的相同，所以这里可以将原本需要从1开始循环判断到n的量缩减到
小于等于sqrt(n)
代码
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function (n) {
var count = 0;
for (var i = 2; i < n; i++) {
if (i == 2) count++;
if (i % 2 == 0) continue;
var isPrime= true;
for (var j = 3; j <= Math.sqrt(i); j += 2) {
if (i % j === 0) {
isPrime= false;
break;
}
}
if (isPrime) {
count++;
}
}
return count;
};
