优化代码以更快地进行因式分解？

Question

我希望让这段代码更快。它会返回一个长数字的所有因子（质数）。如果 longNumber 是特定的一个数字，执行时间显然需要几分钟。

int div = 2;
String factors = "";

while (longNumer != 1)
{
    if (longNumer % div == 0)
    {
        longNumer /= div;
        factors += div + " ";
    }
    else { div++; }
}

//longNumber = 10, gives: 2 5. 
//longNumber = 150, gives: 3 5 7.
//longNumber = 10523, gives: 17 619.

对于像“7544222046562688368”这样的数字，处理时间太长，这并不好。您有什么建议吗？

- Matt

---

使用记忆化技术来处理质数，可以提高代码性能。 - Luiggi Mendoza

如果你的算法真的将150的因数给出为3,5,7，我建议你在浪费时间让它更快之前先把它修正正确。 - High Performance Mark

Answer 1

对于大数字，您可以使用埃拉托色尼筛法算法首先找到sqrt(n)以下的素数，然后您必须检查这些素数是否是因子。

- Rahul Tripathi

---

这对于64位数字帮助不大，仍然有很多素数在2^32以下需要检查，并且生成它们将会带来递减的回报。 - IVlad

使用厄拉多塞筛法获取前sqrt(n)个质数需要大约sqrt(n)loglog n次操作。试除法需要sqrt(n)次操作。使用筛法你能得到什么好处？ - Douglas Zare

@DouglasZare 是的，筛法比试除法需要更多的操作次数。但是所涉及的操作非常不同。对于CPU而言，除法比加法慢大约10倍，而log(log(n))在您可以放入长整型数据范围内实际上是恒定的。 (且该常数显著小于10)。您选择的编程语言可能会增加足够的开销来掩盖这种性能差异。但在高效的编程语言中，一个良好实现的筛法很可能会在任何可以放入长整型数据范围内击败试除法。 - btilly

@btilly：我认为一个几乎优化的筛法不是一个公平的比较，因为优化筛法比这个问题要难得多。对于相同的限定范围，通过避免试除小质数的倍数（筛法高效的一个要素）就能获得筛法的很大好处。此外，通过提前停止计算，而不需要缩小质数集合的范围，你还能获得更多好处。我见过的筛法实现并没有设计成这样，尽管它们可以进行修改来实现这一点。 - Douglas Zare

@DouglasZare 几年前我在解决欧拉计划问题时，用 Perl 实现了一个筛法算法，它以流的形式返回，并且在相同语言中比试除法快得多。而且这段代码写起来也不太难。 - btilly

Answer 2

在实现比试除法更快的分解算法之前，一个容易纠正的错误是避免在最后一块的sqrt过程中进行试除。

while (longNumber != 1) {
    if (longNumber % div == 0) {
        longNumber /= div;
        factors += div + " ";
    }
    else {
        if (div*div>longNumber) {
            if (longNumber > 1)
                factors += longNumber + " ";
            break; // leave the while loop.  
        } 
        div++; 
    }
}

让最大的两个质因数为P1和P2。在您的版本中，您大约进行了c P1次操作。在修改后的版本中，您大约进行了c Max(sqrt(P1),P2)次操作。对于7544222046562688368，改进应该是45倍。

另一个改进是更改div++行。您不需要尝试除以大于2的偶数或可被3整除的大于3的数字。避免这些可以将计算速度提高多达2倍以上，并且通过避免测试其他小素数的倍数可以略微提高效率。但是，您不想花时间对div进行小素数的试除。相反，您可以跟踪当前和允许的余数mod 2 * 3 * 5 * 7。这称为使用小素数轮子。

一些其他答案已经谈到了使用筛法找到所有小素数，然后仅通过这些进行试除。如果您只要分解一个数字，这并没有帮助，因为筛选出素数太长了。生成sqrt(n)以下的素数列表大约需要c sqrt(n) loglog n次操作，而对sqrt(n)以下的所有内容进行试除大约需要c sqrt(n)次操作。如果您需要分解许多大型数字，则执行一次筛法并存储结果可能会有所帮助。

- Douglas Zare

---

我认为 div*div > longNumber 不可能成立，因为在这种情况下，您已经找到了所有的质因数，并且 longNumber 已经被减少到 1。 - Paul Hankin

@匿名用户：当你只剩下一个质因数时，divdiv可能大于longNumber。假设longNumber从7开始。你测试div=2，然后div=3，33>7，然后你知道7是质数，所以你不需要测试任何更高的div值。如果longNumber从14开始，你找到2的因子，将其减少到7，再次测试2，然后在3处停止。 - Douglas Zare

Answer 3

你可以使用以下步骤 - 1. 找到所有小于等于sqrt(longNumber)的质数，并将它们保存在一个数组中 - primes。 2. 现在逐渐使用数组元素 - primes 作为除数来找到因子。

- Razib

---

循环遍历数组在性能方面不是很差吗？ - OPK

@HashMap并不是最好的选择。它取决于数组有10个元素还是100万个元素，这决定了性能的好坏。 - Luiggi Mendoza

我认为只有在质数未存储在数组中时，你才应该寻找它们。如果你将质数以排序的方式存储在数组中，你可以通过使用二分查找来快速查找。 - Luiggi Mendoza

sqrt(longNumber) 仍然是一个长整数。对于64位数字来说，这并没有太大帮助，因为仍有很多小于 2^32 的质数需要检查，并且生成它们将会逐渐减少收益。 - IVlad

Answer 4

建议使用Eratosthenes筛法并不能解决你描述的这种数字。对于64位数字，sqrt（2 ^ 64）= 2 ^ 32，仍然很大。

对于这些数字，您最好选择{{link1：Pollard's Rho算法}}或更复杂的整数分解方法，列在{{link2：此处}}中：

代数群因式分解算法，其中包括Pollard的p-1算法，Williams的p + 1算法和Lenstra椭圆曲线因式分解

费马因式分解方法

欧拉因式分解方法

特殊数域筛法

- IVlad

Answer 5

一种简单易行且实际效率较高的因式分解64位整数的方法，是将试除法和Pollard's rho算法结合起来。以下是伪代码：

function factors(n)
    wheel := [1,2,2,4,2,4,2,4,6,2,6]
    w, f, fs := 0, 2, []
    while f*f <= n and f < 10000
        while n % f == 0
            fs, n := f :: fs, n / f
        f, w := f + wheel[w], w+1
        if w = 11 then w = 3
    if n == 1 return fs
    h, t, g, c := 1, 1, 1, 1
    while not isPrime(n)
        repeat
            h := (h*h+c) % n # the hare runs
            h := (h*h+c) % n # twice as fast
            t := (t*t+c) % n # as the tortoise
            g := gcd(t-h, n)
        while g == 1
        if isPrime(g)
            while n % g == 0
                fs, n := g :: fs, n / g
        h, t, g, c := 1, 1, 1, c+1
    return n :: fs

这个程序使用2、3、5轮进行试除法，最高可达10000，然后采用rho算法的简单实现；它可以在几毫秒内将你的样本数分解为7544222046562688368 = 2 * 2 * 2 * 2 * 7 * 7 * 14618561 * 658254407。虽然还有改进空间，但这已足以让你开始了。

- user448810