Project Euler #3，因分解因子造成无限循环

Question

我正在做Project Euler的题目，因为我真的需要练习写代码，而且我的数学技能生疏得像锈铁一样。所以我选择了Project Euler。我相信这里大多数人都听说过这个问题，但我还是把它写在这里以便完整：

13195的质因数是5、7、13和29。那600851475143这个数字的最大质因数是什么呢？

为了解这个问题，我写了两个函数：

from math import sqrt

def isprime(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n % 2 == 0:
        return False
    for x in range(3, round(sqrt(n))+1, 2):
        if n % x == 0:
            return False
    else:
        return True

这个函数主要是用来检查输入的数字是否是质数。它的工作原理应该是没问题的（至少我认为是这样），不过现在说了这句话我又开始怀疑了。无论如何，它首先会检查一些特殊情况：1（永远不是质数）、2（是质数）或者这个数字是否能被2整除（如果能，那就不是质数）。如果没有遇到这些特殊情况，它就会进行一个普通的质数测试。

这是我的因数分解代码：

def factorization(n):
   factor = 2
   x = 3
   while True:
       if n % x == 0:
           if isprime(x):
               factor = x
               n = n // x
               if n == 1:
                   return factor
           else:
               return factor
       x += 2

这个代码显然没有按预期工作。遗憾的是，它在解决Project Euler的特定值时是有效的，但对于像100这样的数字就不行。我不太确定该怎么修复这个问题：问题是如果输入的是100，它会正确找到前面的5（2*2*5），但之后就会循环到7，这样整个过程就会无限循环，因为答案是2*2*5*5。使用递归会有帮助吗？我试过，但结果并没有变得更好（对于某些数字，它仍然会进入无限循环）。我现在不太确定该怎么解决这个问题。

Answer 1

对于那些重复的（奇数）因子，当找不到一个可以整除的数时，就把x加一。

def factorization(n):
    factor = 2
    x = 3
    while True:
        if n % x == 0:
            if isprime(x):
                factor = x
                n = n // x
                if n == 1:
                    return factor
            else:
                return factor
        else:
            x += 2

OTOS，看起来你总是漏掉“2”这个因子。把它放在最前面，然后再进行主要的循环。

编辑（根据评论）

你可以做得简单得多：

def factorization(n):
    factors = []
    x = 2
    while True:
        while n % x == 0:
            factors.push(x)
            n /= x
        if n == 1:
            return factors
        if x == 2:
            x = 3
        else: 
            x += 2

Answer 2

我觉得你把问题搞得比实际复杂了。

这里有一些伪代码，你应该能把它转成Python代码。

from itertools import count
n=600851475143  
for x in count(2):
    while x divides n:
        divide n by x
    if n==1:
        print x # largest factor will be the last one
        break

Answer 3

你走在正确的道路上，但需要考虑到可能会有重复的因子。你可以用下面这样的方式来处理：

factors = []

while num % 2 == 0:
  factors.append(2)
  num /= 2

这里的意思是，你会不断地把2加到因子列表中，直到你测试的那个数字变成奇数为止。你也可以用类似的逻辑来处理其他因子，这样可以让你的因数分解方法更完善。