javascript - 精度和大数

Question

我用 JavaScript 编写了一个函数来计算素数:

function isDivisible(dividend, divisor) {
    return dividend % divisor === 0;
}

function isPrime(n) {
    var factor = 2;

    n = Math.abs(n);

    if (n <= 1) {
        return true;
    }

    while (factor < n) {
        if (isDivisible(n, factor)) {
            return false;
        }

        factor += 1;
    }

    return true;
}
function getPrimes(max) {
    var primes = [], i = 1;

    while (i <= max) {
        if (isPrime(i)) {
            primes.push(i);
        }

        i += 1;
    }

    return primes;
}

function M(p) {
    return Math.pow(2, p) - 1;
}

function isMersennePrime(p) {
    var s, m, i;

    s = 4;
    m = M(p);

    for (i = 0; i < p - 2; i++) {
        s = (s * s - 2) % m;
    }

    return s === 0 ? true : false;
}

function findLargestMersennePrime(pMax) {
    var p, primes = getPrimes(pMax);

    while (primes.length) {
        p = primes.pop();

        if (isMersennePrime(p)) {
            return M(p);
        }
    }

    return null;
}

函数 findLargestMersennePrime 接受参数 p，它用作计算梅森素数 M(p) 的种子值。该程序使用 Lucas Lehmer Primality test .

我使用的测试用例对应于this table .对于任何给定的输入 pMax，程序会获取小于或等于 pMax 的素数列表，然后检查 p 的梅森数是否为素数。测试用例通过了前 7 个梅森素数，即 p < 31。

当 p = 31, 61, 89... 时，M(p) 为素数，但函数 isMersennePrime(31) 始终返回 false。

我认为这可能与 JavaScript 中数字的最大大小有关。我正在运行 Node 0.5。这是我的代码中的错误还是 JavaScript 的限制？是否有另一种语言更适合解决此问题或使其在 JS 中工作的方法？

Answer 1

Javascript 数字是标准的 double precision floating numbers并且可以达到 2⁵² - 1。这对于您的第 8 个梅森素数应该足够了(但对于第 9 个梅森素数来说不够精确)