时间戳

首页 > 解决方案 > Javascript - 素数函数问题，内存过载

javascript - Javascript - 素数函数问题，内存过载

问题描述

我有下一个问题。我试图找到所有素数，直到指定的数字作为输入，但是当我输入例如非常大的数字（例如 13480000 或 643513511）时，算法会以某种方式停止迭代，并且我的浏览器在处理函数方面变得太慢. 这是html代码：

<!DOCTYPE html>
<html lang="es">
<head>
<script src="esPrimo.js">
</script>
</head>
<body>
<h1>Lista de primos</h1>
<form name="formu">
    <input id="txtValue" type="text" />
    <input type="button" value="Calcular!" onclick="proceso()">
</form>

<p id="res">El resultado se escribe aqui</p>
</body>
</html>

这是我的 esPrimo.js 文件的 javascript 代码

function proceso() {
    var value = document.querySelector('#txtValue').value;
    var primos = getPrimos(value);
    var output = document.querySelector('#res');
    output.innerHTML = primos.toString();

}

function getPrimos (value) {
    var primos = [];
    for (var i = 1; i <= value; i++){
        if (esPrimo(i)) primos.push(i);
    }
    return primos;
}

function esPrimo(n){
     if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false; 
        var m = Math.sqrt(n);
        for (var i = 2; i <= m; i++)
            if (n % i == 0) return false;
        return true;
}

在程序获取参数的最后一个函数上，变得非常慢。它检查 n 是否可以被每个整数 2、3、4、5 ... 整除，直到 sqrt(n)，但这个版本的代码行数最少。此外，我尝试了另一种遍历所有素数的方法，例如：

function esPrimo(n) {
if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false; 
 if (n%2==0) return (n==2);
 var m=Math.sqrt(n);
 for (var i=3;i<=m;i+=2) {
  if (n%i==0) return false;
 }
 return true;
}

在这里，它分别检查除数 2：然后，它只检查奇数除数，从 3 到 sqrt(n)。最多检查 3 和 sqrt(n) 之间的数字的一半。

我怎样才能优化代码，以便我的程序能够更快地计算这种迭代？

任何建议或建议，这将是非常感激和有帮助的，因为我在过去一周一直试图以某种方式找到解决方案，但它没有用。此外，我还有最后一个感兴趣的链接，我深入研究并帮助了我很多，我想说的是在掌握数字的素性检验方面。

Javascript素性测试

谢谢

标签： javascripthtmlprimes

解决方案

与 Pointy 在评论中所说的不同，下面是您的 JavaScript 重构以使用 Eratosthenes “筛子”算法。在我进入代码之前，首先快速解释一下 Erastosthenes。Erastosthenes 发现您可以更有效地找到介于 2 和 N 之间的素数，其中 N 是一个大数，方法是找到两者之间每个数字的倍数并将它们从列表中删除。你剩下的东西一定是素数。

EG N = 10

2、3、4、5、6、7、8、9、10 --> 2 的倍数包括 4、6、8 和 10，所以它们不是素数。3 的倍数包括 6 和 9，因此它们被删除。等等。你最终只剩下 2、3、5、7，其中没有一个有一个数字相乘。

现在，下面的代码使用了 Erastosthenes 算法，但是如果你尝试你的 643513511 的例子，它仍然会中断，我只是觉得浏览器需要的处理能力太多了，但我可能错了。但是，它适用于您的 1300 万示例。

注意：此代码是使用您的代码和从另一篇 Stackoverflow 帖子中获取的代码重构的，即 Sieve of Eratosthenes algorithm in JavaScript running never for large number。

var getPrimos = function(n) {
    // Eratosthenes algorithm to find all primes under n
    var array = [], upperLimit = Math.sqrt(n), output = [];

    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++) {
        array.push(true);
    }

    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) {
                array[j] = false;
            }
        }
    }

    // All array[i] set to true are primes
    for (var i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

推荐阅读