计数质数

[Aras-ax]

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

示例:

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

解答

一个数如果是质数，那么他的倍数肯定都不是质数

function countPerim(n) {
    let hash = {},
        count = 0;
    for (let i = 2; i < n; i++) {
        if (hash[i]) {
            continue;
        }

        count++;
        for (let j = i; j < n; j = j + i) {
            hash[j] = true;
        }
    }
    return count;
}