寻找素数.md

寻找素数

如何高效寻找素数

首先是直接for循环

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

这种方式时间复杂度是O(n^2)，太高了，优化一下

const countPrimes = function (n) {
    let isPrim = Array.from({length: n}).fill(true);

    for (const i = 2; i < n; i++) {
        if (isPrim[i]) {
            // i 的倍数不是素数
            for (var j = 2 * i; j < n; j++) {
                isPrim[i] = false;
            }
        }
    }
    
    let count = 0;
    for (const i = 2; i < n; i++) {
        if (isPrim[i]) {
            count++;
        }
    }
    
    return count;
}

上面这种会造成重复运算的过程，仍然存在冗余计算 比如 n = 25，i = 4 时算法会标记 4 × 2 = 8，4 × 3 = 12 等等数字， 但是这两个数字已经被 i = 2 和 i = 3 的 2 × 4 和 3 × 4 标记了。

我们可以稍微优化一下，让 j 从 i 的平方开始遍历，而不是从 2 * i 开始：

说实话我不知道怎么就突然可以从平方开始遍历，这样的逻辑是什么也没说啊

const countPrimes = function (n) {
    let isPrim = Array.from({length: n}).fill(true);

    for (const i = 2; i < n; i++) {
        if (isPrim[i]) {
            // 这里就直接让 j = i * i 了，然后 j += i 来进行递增
            for (var j = i * i; j < n; j += i) {
                isPrim[i] = false;
            }
        }
    }
    
    let count = 0;
    for (const i = 2; i < n; i++) {
        if (isPrim[i]) {
            count++;
        }
    }
    
    return count;
}