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

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

Answer 1

看起来人们在做项目Euler的事情，你自己编写解决方案。对于所有想完成工作的人来说，primefac模块可以非常快速地完成大量数据：

#!python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))

Answer 2

好啊所以你说你了解基本知识，但你不确定它到底是如何工作的。首先，这是对项目Euler问题的一个很好的回答。我对这个问题做了很多研究，这是迄今为止最简单的回答。

为了便于解释，我让n=20。要运行真正的Project Euler问题，请让n=600851475143。

n = 20 
i = 2

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

print (n)

此说明使用了两个while循环。关于while循环，要记住的最大一点是，它们一直运行，直到不再是true。

外部循环指出，虽然i*i不大于n（因为最大质因数永远不会大于n的平方根），在内部循环运行后将1添加到i。

内部循环指出，当i均匀划分为n时，将n替换为n除以i。此循环连续运行，直到不再为真。对于n=20和i=2，n被替换为10，然后再次被5。因为2不均匀划分为5，循环以n=5停止，外循环结束，产生i 1=3。

最后，由于3squared大于5，外部循环不再是true，并打印n的结果。

谢谢你发布这个。在意识到它是如何工作的之前，我一直在看代码。希望这是您在回复中寻找的内容。如果没有，请告诉我，我可以进一步解释。

Answer 3

这个问题是我在谷歌上搜索“python质数分解”时弹出的第一个链接。正如@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