项目Euler #3最大素数因子

Question

给定的

13195的素因子为5、7、13和29。数字600851475143中最大的素因子是什么？

解决方案

def max_factor(num):
    """Find the maximum prime factor."""
    factor = 2
    while factor * factor <= num:
        while num % factor == 0:
            num /= factor
        factor += 1
    if (num > 1):
        return num
    return factor
    
print max_factor(33) #11
print max_factor(38) #19
print max_factor(600851475143) #6857

这个问题已经讨论了很多。我更感兴趣的是寻找运行时间的复杂性。因为这里的输入只是一个数字，所以如何将运行时间与输入大小联系起来。而且，我感觉到运行时间应该是对数的，但是如何精确地得到它似乎相当困难。

Answer 1

而且，我感觉到运行时间应该是对数的，但是如何精确地得到它似乎相当困难。

不，运行时间是O(\sqrt N) 最坏的情况。考虑一个素数的情况(或特别糟糕的情况，如孪生素数的乘积)。您必须检查\sqrt N 可能的值才能找到答案。没办法绕过那个。

就代码而言，您有一个bug，否则只会有一些微小的/琐碎的注释。首先是窃听器。问题是：

return factor

最后的factor是什么？它只是第一个正方形大于任何num的数字。它不一定是原始值的factor。只是个索引。例如，max_factor(8) == 3、max_factor(9) == 4等，您需要跟踪哪些尝试因素实际上是因素。类似于：

def max_factor(num):
    """Find the maximum prime factor."""
    best = None
    factor = 2 
    while factor * factor <= num:
        while num % factor == 0:
            best = factor
            num /= factor
        factor += 1
    if (num > 1): 
        return num 
    return best

正如其他人所指出的，您不进行输入验证。在这里，我并不认为这是非常重要的，只要求用户输入合理的数字是非常好的。但只要把这句话说出来就没什么坏处了：

def max_factor(num):
    """Find the maximum prime factor."""
    assert num >= 2
    ...

否则，您将有一个具有非平凡条件的计数循环.这是用Python来表达的最烦人的事情之一。在C或C++中，这将是：

for (factor=2; factor*factor <= num; ++factor) { ... }

我们把一切都放在一条线上。在Python中，我们有三种选择，其中没有一种是我感兴趣的。你的：

factor = 2
while factor * factor <= num:
    ...
    factor += 1

使用itertools.count：

for factor in itertools.count(start=2):
    if factor * factor > num: break
    ...

使用itertools.takewhile和count()：

for factor in itertools.takewhile(lambda f: f*f <= num, itertools.count(start=2)):
    ...

是的，即使我们把一切都放在一条线上，我也不确定这有什么用。嗯。

最后，因素检验。您正在检查的因素依次为：

2, 3, 4, 5, 6, 7, 8, ...

这是相当低效的。首先，一旦检查了2，就不需要检查任何偶数。同样，对于3和3的倍数，更有效的检查是：

2, 3 then 5, 7, 11, 13, 17, 19, 23, ... 

从那时起，基本上交替添加2和4。我们最后得到的只是奇数，而不是3的倍数。因此，我们只需要检查每6个数字中的2个。我们可以为此编写一个生成器：

def potential_factors(num):
    yield 2
    yield 3

    fact = 5
    incr = 2
    while fact * fact <= num:
        yield fact
        fact += incr
        incr ^= 6

我们可以使用：

def max_factor_mine(num):
    assert num >= 2

    def potential_factors():
        yield 2
        yield 3

        fact = 5 
        incr = 2 
        while fact * fact <= num:
            yield fact
            fact += incr
            incr ^= 6

    best = None
    for factor in potential_factors():
        while num % factor == 0:
            best = factor
            num /= factor

    return num if num > 1 else best

这和你用这种方法得到的效果差不多。如果你想要更好的性能，你必须得到一个不同的算法。在这个答案中，我向您展示了一种使用波拉德氏肌的方法，只要做一些完全不同的事情，就能显着地提高性能：

+---------------------+----------+--------------------+---------+
|                     | OP       | OP w/fewer factors | Pollard |
+---------------------+----------+--------------------+---------+
| 600851475143        |  0.003s  |  0.002s            |  0.092s |
| 145721 * 145723     |  0.298s  |  0.174s            |  0.018s |
| 1117811 * 1117813   |  2.286s  |  1.331s            |  0.262s |
| 18363797 * 18363799 | 40.379s  | 21.895s            |  0.825s |
+---------------------+----------+--------------------+---------+

Answer 2

您不执行任何参数验证，所以看看当我执行以下操作时会发生什么：

>>> f(1)
2
>>> f(0)
2
>>> f(-12312321)
2

避免这种情况的简单方法是

def max_factor(num):
    if num < 2:
        raise ValueError("Only numbers greater than 1 are allowed.")

或者，如果每一种情况都是算法的可接受输入，您可以处理它们(我不确定这里的数学)。0和1很容易，因为如果它们被认为是有效的，它们是它们自己的因素：

if num in (1, 0):
    return num

对于负数，您需要num为正，以便您的算法工作。您可以使用abs将其变为正数。在此之前，您只需设置一个检查负参数的布尔值，然后在最后检查这个值，看看是否返回一个负数。

negative = num < 0
num = abs(num)

...

if (num > 1):
    return num if not negative else -num
return factor if not negative else -factor

无论您认为是有效的输入，都应该在docstring中注明，这样人们就不必尝试传递参数来查看什么是可允许的。

def max_factor(num):
    """Find the maximum prime factor for num > 1."""

我也认为对于不熟悉它的人来说，这是一个复杂的算法。我不得不阅读维基百科页面的最大主要因素，以了解这是如何运作的。一些关于它背后的方法的评论可能很难管理，但是引用它是一种已知的算法让人们去查找，至少会给他们提示，因为它是Googleable，而不是你发明的东西。

Answer 3

1. 你应该经常问一下角落里的箱子是什么。您希望max_factor(1)返回什么？
2. 你的代码有问题。您有return fact，但是fact没有被分配到任何地方。如果您按照注释中的建议将其更改为return factor，那么它仍然是错误的：max_factor(8) 会回来3。