js实现素数

判断素数的基本方法

素数是大于1的自然数，除了1和它本身外没有其他约数。在JavaScript中，可以通过以下方法实现素数判断：

方法一：基础遍历法
通过遍历2到n-1之间的所有数，检查是否能被整除：

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

缺点：效率较低，时间复杂度为O(n)。

优化方法：平方根范围

数学上，若n不是素数，其约数之一必然小于或等于√n。因此只需遍历到√n即可：

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

优点：时间复杂度优化至O(√n)。

生成素数列表

基于上述方法，生成指定范围内的素数列表：

function generatePrimes(max) {
    const primes = [];
    for (let i = 2; i <= max; i++) {
        if (isPrime(i)) primes.push(i);
    }
    return primes;
}

更高效的算法：埃拉托斯特尼筛法

适用于生成大量素数，通过标记非素数来提升效率：

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;
    }, []);
}

优点：时间复杂度为O(n log log n)，适合大规模计算。

实际应用示例

检查数字17是否为素数：

console.log(isPrime(17)); // 输出: true

生成100以内的素数列表：

console.log(sieveOfEratosthenes(100)); // 输出: [2, 3, 5, ..., 97]