ProjectEuler#3，因式分解的无限循环

Question

所以我在做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整除（不是素数）。如果没有任何特殊情况发生，它将运行一般素性测试。在

这是我的分解代码：

^{pr2}$

这绝对不是我们想要的。不幸的是，它是为projecteuler问题的特定值而工作的，但它不适用于100。我不确定我需要做些什么来解决这个问题：如果它是一个像100的数字，它会正确地找到前5（2*2*5），但之后会循环并设置x=7，这将使整个事情无限循环，因为答案是2*2*5*5。递归在这里有帮助吗？我试过了，但没有变得更漂亮（对于某些数字，它仍然会进入一个无休止的循环）。我现在不知道怎么解决这个问题。在

Answer 1

你在一个很好的轨道上，但你需要考虑到重复因素的可能性。你可以这样做：

factors = []

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

这里的想法是，你将继续在因子列表中添加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

对于重复（奇数）因子，如果没有找到除数，只需增加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

奥托斯，看来你总是错过“2”因素。把它们粘在上面，然后做主循环

编辑（评论后）

你可以做得更简单：

^{pr2}$