时间戳

首页 > 解决方案 > 最大素数函数工作太慢

javascript - 最大素数函数工作太慢

问题描述

我已经编写了找到某个数字的最大素数的函数。此功能有效，但问题是它太慢了。例如，当我输入 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));

标签： javascriptfunctionprimes

解决方案

好吧，在我们进入之前，让我们先整理一下理论。在数学上，您测量特定代码运行时间的方式由O(n)表示法（big-o 表示法）表示，其中n是输入的大小。

您的测试素数函数具有所谓的含义，随着（在这种情况下，您的数字输入）linear complexity的大小变大，它会线性变慢。n

对于 number 15，执行上下文如下：

15 % 2 == 0 (FALSE)
15 % 3 == 0 (TRUE)
...
15 % 14 == 0 (FALSE)

这意味着对于 number 100，将有 98 (2 - 99) 步。这会随着时间的推移而增长。让我们考虑一下您的号码：600851475143。程序将执行600851475143；将for-loop获得触发600,851,475,141次数。

现在，让我们考虑一个时钟周期。假设每条指令需要2 次1 clock cycle，而循环的简化版本需要 2 次，这个数字600851475143将执行1,201,702,950,286次数。考虑每个时钟周期需要0.0000000625几秒钟（对于Arduino等 16-MHz 平台），仅该代码所花费的时间是：

0.0000000625 * 1201702950286 = ~75,106 seconds

或周围20 hours。

你知道我要去哪里。

让该程序更快运行的最佳方法是使用概率测试并使用此数字（或其 BigInteger 变体）确认您的发现。

您的方法更加线性，因为for-loop检查素数的迭代次数随着数量的增加而增加。您可以将 CPU 周期时间与数字一起绘制，您会发现这是一种相当低效的方法。

我在我的大学有离散数学，所以只是一个警告 - 当你进入越来越快的测试的乌托邦时，素数测试及其变体变得非常混乱。这是一条充满数学荆棘的道路，您应该在穿越丛林时系好安全带！;)

如果您需要这方面的更多信息，我很乐意为您提供帮助！我希望这有帮助！:)

推荐阅读