我已经编写了查找某个数的最大质因数的函数。这个功能有效,但问题是它太慢了。例如,当我输入 600851475143 作为参数时,寻找最大质因数的过程持续时间太长。我怎样才能修改它以使其工作得更快? 这是我的代码:
class test {
static addArray(someArray, member) {
for (var i = 0; i <= someArray.length; i++) {
if (i == someArray.length) {
someArray[i] = member;
return someArray;
}
}
}
static someLength(someArray) {
var i = 0;
while (someArray[i] !== undefined) {
var lastItem = i;
i++;
}
return i;
}
static testPrime(i) {
for (var k=2; k < i; k++) {
if (i % k == 0) {
return false;
}
}
return true;
}
}
var primeArray = [];
function largestPrime(n) {
for (var i=2; i < n; i++) {
//var k = n / i;
if (n % i == 0 && test.testPrime(i) == true) {
test.addArray(primeArray, i);
n == n / i;
}
}
return primeArray[test.someLength(primeArray) - 1];
}
document.write(largestPrime(600851475143));
最佳答案
好吧,在我们开始之前,让我们先梳理一下理论。衡量一段特定代码运行时间的方法在数学上用 O(n)
表示法(big-o 表示法)表示,其中 n
是输入的大小。
你的测试素函数是一种叫做线性复杂度
的东西,这意味着它会随着 n
的大小(在这种情况下,你的数字输入)变得线性变慢大的。
对于数字15
,执行上下文如下:
15 % 2 == 0 (FALSE)
15 % 3 == 0 (TRUE)
...
15 % 14 == 0 (FALSE)
这意味着对于数字 100
,将有 98 (2 - 99) 步。这会随着时间的推移而增长。让我们考虑一下您的电话号码:600851475143
。该程序将执行600851475143
; for 循环
将被触发 600,851,475,141
次。
现在,让我们考虑一个时钟周期。假设每条指令占用 1 个时钟周期
,而循环的简化版本占用 2 个时钟周期,则数字 600851475143
将执行 1,201,702,950,286
次。考虑到每个时钟周期需要 0.0000000625
秒(对于 16 MHz 平台,例如 Arduino ),该代码单独花费的时间是:
0.0000000625 * 1201702950286 = ~75,106 seconds
或大约 20 小时
。
你知道我要去哪里了。
让这个程序运行得更快的最好方法是使用 probabilistic test并使用此数字(或其 BigInteger 变体)确认您的发现。
您的方法更线性,因为 for-loop
检查素数的迭代次数随着次数的增加而增加。您可以将 CPU 周期时间与数字一起绘制出来,您会发现这是一种相当低效的方法。
我在我的大学学习离散数学,所以只是一个警告——当你进入越来越快的测试乌托邦时,素数测试和它们的变体会变得非常困惑。这是一条充满数学荆棘的道路,穿越丛林时你应该系好安全带! ;)
如果您需要这方面的更多信息,我很乐意提供帮助!我希望这有帮助! :)
关于javascript - 最大质因数函数运行速度太慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52243186/