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

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