js 实现现实素数

判断素数的方法

素数是指大于1的自然数，除了1和它本身外，不能被其他自然数整除。以下是几种常见的判断素数的方法。

基础方法

通过遍历2到n-1之间的所有整数，检查是否有能整除n的数。如果没有，则n是素数。

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

优化方法一

只需要检查2到√n之间的整数即可，因为如果n有大于√n的因数，必然有小于√n的对应因数。

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

优化方法二

排除偶数的情况，因为除了2以外的偶数都不是素数。

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

生成素数列表

如果需要生成一定范围内的所有素数，可以使用筛法。

埃拉托斯特尼筛法

function sieveOfEratosthenes(max) {
    const sieve = new Array(max + 1).fill(true);
    sieve[0] = sieve[1] = false;
    const sqrtMax = Math.sqrt(max);
    for (let i = 2; i <= sqrtMax; i++) {
        if (sieve[i]) {
            for (let j = i * i; j <= max; j += i) {
                sieve[j] = false;
            }
        }
    }
    const primes = [];
    sieve.forEach((isPrime, num) => {
        if (isPrime) primes.push(num);
    });
    return primes;
}

实际应用示例

console.log(isPrime(7)); // true
console.log(isPrime(10)); // false
console.log(sieveOfEratosthenes(20)); // [2, 3, 5, 7, 11, 13, 17, 19]

这些方法可以高效地判断和生成素数，适用于不同的需求场景。