内容

统计所有小于非负整数 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;
};

回到目录