原题描述

原题链接

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

示例 1：

输入：n = 10

输出：4

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

示例 2：

输入：n = 0

输出：0

示例 3：

输入：n = 1

输出：0

提示：

0 <= n <= 5 * 106

个人解法

Java

JavaScript

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

更优解法

Java

JavaScript

const isPrime = (x) => {
    for (let i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
var countPrimes = function(n) {
    let ans = 0;
    for (let i = 2; i < n; ++i) {
        ans += isPrime(i);
    }
    return ans;
};