Python 寻找质因数

Question

两部分问题：

1. 试图确定 600851475143 的最大质因数，我在网上发现这个程序似乎有效。问题是，我很难弄清楚它到底是如何工作的，尽管我了解程序正在做什么的基础知识。另外，我希望您能阐明您可能知道的寻找主要因素的任何方法，也许无需测试每个数字，以及您的方法是如何工作的。

这是我在网上找到的素数分解 代码 [注意：此代码不正确。请参阅下面 Stefan 的回答以获得更好的代码。] ：

 n = 600851475143
i = 2
while i * i < n:
     while n % i == 0:
         n = n / i
     i = i + 1

print(n)

#takes about ~0.01secs

1. 为什么这段代码比这段代码快这么多，这只是为了测试速度，除此之外没有其他真正目的？

 i = 1
while i < 100:
    i += 1
#takes about ~3secs

原文由 francium 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这个问题是我用谷歌搜索时弹出的第一个链接 "python prime factorization" 。正如@quangpn88 所指出的，此算法对于诸如 n = 4, 9, 16, ... 之类的完美平方是 错误的（！） 但是，@quangpn88 的修复也不起作用，因为如果最大的素因子出现 3 或，它将产生不正确的结果更多次，例如 n = 2*2*2 = 8 或 n = 2*3*3*3 = 54 。

我相信 Python 中正确的暴力算法是：

 def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

不要在性能代码中使用它，但对于中等数量的快速测试来说是可以的：

 In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 µs per loop

如果寻求完全素因数分解，则这是蛮力算法：

 def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

原文由 Stefan 发布，翻译遵循 CC BY-SA 3.0 许可协议