python - Python寻找主要因素

两部分问题:

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

2)为什么该代码比仅用于测试速度并且没有其他实际目的的代码快得多？

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

最佳答案

这个问题是我搜索"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