两部分问题：
- 试图确定 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
- 为什么那个代码比这个代码快这么多，这只是为了测试速度而没有其他真正的目的？
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 or 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
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
