[算法]判断质数

https://leetcode-cn.com/problems/count-primes/solution/ji-shu-zhi-shu-by-leetcode-solution/

枚举

时间复杂度：O(n * sqrt(n))

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

埃式筛 (质数数倍数标记)

时间复杂度：O(nloglogn)

for (let j = i * i; j < n; j += i) {
  isPrime[j] = 0;
}

线性筛

时间复杂度：O(n)

for (let j = 0; j < primes.length && i * primes[j] < n; ++j) {
            isPrime[i * primes[j]] = 0;
            if (i % primes[j] === 0) {
                break;
            }
        }

练习

204. 计数质数

function countPrimes(n) {
    let res = [];
    for (let i = 0; i<n; i++) {
        if (isPrime(i)) {
            res.push(i)
        }
    }
    return res;
}

function isPrime(n) {
    let maxNum = Math.sqrt(n);
    for (let i=2; i<=maxNum; i++) {
        if (n % i == 0) return false;
    }
    return true;
}