质数js实现

判断质数的基本方法

质数是指大于1的自然数，且只能被1和它本身整除。在JavaScript中，可以通过以下方式实现质数判断：

function isPrime(num) {
    if (num <= 1) return false;
    if (num === 2) return true;
    if (num % 2 === 0) return false;

    for (let i = 3; i <= Math.sqrt(num); i += 2) {
        if (num % i === 0) return false;
    }
    return true;
}

优化算法

通过数学优化可以减少循环次数。例如，只需检查到该数的平方根即可，因为如果存在大于平方根的因数，必然对应一个小于平方根的因数。

function isPrimeOptimized(num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 === 0 || num % 3 === 0) return false;

    let i = 5;
    let w = 2;
    while (i * i <= num) {
        if (num % i === 0) return false;
        i += w;
        w = 6 - w; // 交替检查6k±1的形式
    }
    return true;
}

生成质数列表

如果需要生成一定范围内的所有质数，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）：

function sieveOfEratosthenes(max) {
    const sieve = new Array(max + 1).fill(true);
    sieve[0] = sieve[1] = false;

    for (let i = 2; i <= Math.sqrt(max); i++) {
        if (sieve[i]) {
            for (let j = i * i; j <= max; j += i) {
                sieve[j] = false;
            }
        }
    }

    return sieve.reduce((primes, isPrime, num) => {
        if (isPrime) primes.push(num);
        return primes;
    }, []);
}

实际应用示例

这些方法可以用于解决实际问题，例如查找范围内的质数或验证用户输入是否为质数：

console.log(isPrime(17)); // 输出: true
console.log(sieveOfEratosthenes(30)); // 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

通过以上方法，可以高效地实现质数判断和生成质数列表的功能。