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

2）为什么那段代码比这段代码快得多，这只是为了测试速度，没有其他真正的目的？

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

Answer 1

看起来人们在做你自己编写解决方案的欧拉项目。对于所有想完成工作的人来说，有一个primefac module可以非常快速地完成大量工作：

#!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。要运行真正的项目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除以i替换n。这个循环持续运行，直到它不再是真的。对于n=20和i=2，n替换为10，然后再次替换为5。因为2没有均匀地分成5，所以循环以n=5停止，外部循环结束，产生i+1=3。

最后，因为3的平方大于5，所以外部循环不再是true，并打印n的结果。

谢谢你发这个。在意识到代码是如何工作的之前，我一直在看它。希望这是你想要的回应。如果没有，告诉我，我可以进一步解释。

Answer 3

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