判断质数算法js

admin 2026年03月19日 20:02 104 0

判断质数是JavaScript中的基础算法，核心思路是试除法：对于自然数n（n>1），从2遍历到√n，若存在能整除n的数，则n不是质数，否则是质数，可优化处理：先判断n是否为2（唯一偶质数），再排除偶数，从3开始步进2遍历，减少循环次数，边界情况需处理n≤1时直接返回false，该算法时间复杂度O(√n)，适用于中小数判断，大数场景需结合更高效算法（如Miller-Rabin）。

JavaScript质数判断算法：从基础到优化

质数是数学和计算机科学中的基础概念,指大于1的自然数中，除了1和它本身外不再有其他因数的数，在JavaScript开发中，判断一个数是否为质数是常见的算法问题，尤其在数学计算、密码学、算法面试等场景中高频出现，本文将从基础算法出发，逐步优化，最终给出高效且实用的JavaScript实现方案。

质数与基础判断逻辑

什么是质数？

根据定义,质数（素数）需满足两个条件：

大于1；
除了1和它本身外,不能被其他自然数整除。

2是最小的质数（也是唯一的偶质数），3、5、7、11等都是质数，而4、6、8、9等非质数（合数）则存在除1和自身外的因数，质数在密码学（如RSA加密算法）、哈希函数设计以及伪随机数生成等领域有着广泛应用。

最基础的试除法

最直观的判断方法是"试除法"：从2开始，依次检查该数是否能被2到n-1之间的整数整除，如果存在能整除的数，则n不是质数；如果遍历完都没有，则是质数。

function isPrimeBasic(n) {
    if (n <= 1) return false; // 质数必须大于1
    for (let i = 2; i < n; i++) {
        if (n % i === 0) {
            return false; // 能被整除，不是质数
        }
    }
    return true; // 遍历结束无因数，是质数
}

问题分析： 该算法的时间复杂度是O(n)，当n较大时（比如判断10000019是否为质数），循环次数会非常多，性能极差，判断一个100万以内的质数，需要循环近100万次，这在实际应用中是不可接受的。

优化试除法：减少不必要的遍历

优化思路1：只遍历到√n

数学上可以证明：如果一个数n是合数（非质数），那么它一定有一个因数小于或等于√n，判断25是否为质数，只需检查到5（√25=5），因为如果存在大于5的因数，对应的另一个因数必然小于5，之前已经检查过。

function isPrimeOptimized1(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)降低到O(√n)，例如判断10000019（√10000019≈3162），循环次数从10000018次降至3162次，效率提升近万倍。

优化思路2：跳过偶数

除了2,所有偶数都不是质数（因为能被2整除），我们可以先判断n是否为2，再判断是否为偶数，然后从3开始，每次步长加2（只检查奇数），进一步减少循环次数。

function isPrimeOptimized2(n) {
    if (n <= 1) return false;
    if (n === 2) return true; // 2是唯一的偶质数
    if (n % 2 === 0) return false; // 排除其他偶数
    // 从3开始，步长2，只检查奇数
    for (let i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i === 0) {
            return false;
        }
    }
    return true;
}

性能提升： 循环次数直接减半，例如判断10000019时，循环次数从3162次降至1581次，效率再次翻倍。

进一步优化：处理边界与特殊情况

在实际应用中,还需要考虑一些边界情况，确保算法的健壮性：

非整数输入：质数定义针对自然数，如果输入是小数或负数，应直接返回false。
1的特殊处理：1既不是质数也不是合数，需明确返回false。
2的特殊处理：2是最小的质数，也是唯一的偶质数，需单独处理。
大数处理：JavaScript的Number类型可以表示的最大安全整数是2^53-1，对于更大的数需要特殊处理。

function isPrime(n) {
    // 处理非整数、负数、0、1
    if (typeof n !== 'number' || !Number.isInteger(n) || n <= 1) {
        return false;
    }
    // 处理2
    if (n === 2) return true;
    // 排除其他偶数
    if (n % 2 === 0) return false;
    // 从3开始，步长2，遍历到√n
    for (let i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i === 0) {
            return false;
        }
    }
    return true;
}

测试用例：

console.log(isPrime(1));    // false
console.log(isPrime(2));    // true
console.log(isPrime(4));    // false
console.log(isPrime(17));   // true
console.log(isPrime(25));   // false
console.log(isPrime(10000019)); // true（质数）
console.log(isPrime(10000020)); // false（合数）
console.log(isPrime(3.14)); // false（非整数）
console.log(isPrime(-7));   // false（负数）
console.log(isPrime(9007199254740991n)); // false（大整数，需要BigInt处理）

更高效的算法：Miller-Rabin素性测试

对于极大数（比如超过10^18）或者需要频繁判断质数的场景，试除法仍然不够高效，我们可以使用概率性算法——Miller-Rabin素性测试，该算法基于费马小定理和二次探测定理，可以在多项式时间内完成测试，虽然结果可能是概率性的，但通过多次测试可以准确率达到任意接近100%。

Miller-Rabin算法原理

Miller-Rabin算法的基本思想是将n-1分解为d·2^s的形式，然后选择一个基数a，检查a^d mod n、a^(2d) mod n、...、a^(2^(s-1)d) mod n是否满足特定条件。

function isMillerRabinPrime(n, k = 5) {
    // 处理小数字和偶数
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0) return false;
    // 将n-1表示为d * 2^s
    let d = n - 1;
    let s = 0;
    while (d % 2 === 0) {
        d /= 2;
        s++;
    }
    // 进行k次测试
    for (let i = 0; i < k; i++) {
        // 选择一个随机基数a (2 <= a <= n-2)
        const a = Math.floor(Math.random() * (n - 3)) + 2;
        let x = modExp(a, d, n);
        if (x === 1 || x === n - 1) continue;
        let continueTest = false;
        for (let j = 0; j < s - 1; j++) {
            x =

标签： #判断质数 #算法js