JS 判断素数的方法

在 JavaScript 编程中，判断一个数是否为素数是一个常见的基础算法问题。素数，是指在大于 1 的自然数中，除了 1 和它自身外，不能被其他自然数整除的数。掌握判断素数的方法，对于理解算法逻辑和提升编程能力很有帮助。

暴力穷举法

这是最直观的判断方法。其基本思路是，从 2 开始到该数的平方根之间的所有整数进行遍历，检查是否能整除给定的数。如果能找到一个数可以整除它，那么这个数就不是素数。示例代码如下：

function isPrime(num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 === 0 || num % 3 === 0) return false;
    for (let i = 5; i * i <= num; i += 6) {
        if (num % i === 0 || num % (i + 2) === 0) {
            return false;
        }
    }
    return true;
}

在这段代码中，首先对小于等于 1 的数直接返回 false，因为素数定义在大于 1 的自然数范围内。对于 2 和 3 直接返回 true。然后排除能被 2 或 3 整除的数。最后，通过从 5 开始，每次增加 6 的方式，检查是否存在能整除 num 的数。

埃拉托色尼筛法

这种方法适合用于找出一定范围内的所有素数。它的原理是，先将所有候选数标记为素数，然后从 2 开始，将 2 的倍数全部标记为非素数，接着对下一个未被标记的数（即 3），将其倍数全部标记为非素数，以此类推。代码示例如下：

function sieveOfEratosthenes(n) {
    let primes = new Array(n + 1).fill(true);
    primes[0] = primes[1] = false;
    for (let i = 2; i * i <= n; i++) {
        if (primes[i]) {
            for (let j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
    let result = [];
    for (let i = 2; i <= n; i++) {
        if (primes[i]) {
            result.push(i);
        }
    }
    return result;
}

这段代码首先创建一个长度为 n + 1 的布尔数组 primes，初始化为全部为 true。然后逐步将非素数标记为 false。最后，遍历数组，将所有标记为 true 的索引值加入结果数组并返回。

掌握这些判断素数的方法，无论是处理数学问题、数据筛选还是算法优化，都能为我们的 JavaScript 编程工作提供有力支持。