我有下一个问题。我正在尝试查找所有素数,直到指定的数字作为输入为止,但是当我输入例如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)之间的数字的一半。
我如何能够优化代码,以便我的程序能够更快地计算这种迭代?
[任何建议或意见,这将是非常有益和有益的,因为上周我一直试图找到某种解决方案,但这没有用。此外,在掌握数字的素数检验方面,我有最后一个感兴趣的环节,我对此进行了深入研究并为我提供了很多帮助。
谢谢
与Pointy在评论中所说的不一样,以下是您的JavaScript重构为使用Eratosthenes的“筛子”算法。在阅读代码之前,请先简要介绍一下Erastosthenes。 Erastosthenes发现,通过找到两个数字之间的每个数字的倍数并将它们从列表中删除,您可以更有效地找到2到N之间的质数,其中N是一个大数。无论剩下什么,都必须是首要的。
例如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 endless 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;
};