Project Euler #3，因式分解的无限循环 [英] Project Euler #3, infinite loop on factorization

问题描述

所以我正在做 Project Euler，因为亲爱的上帝，我需要练习编写代码，而且我的数学技能非常生疏.因此；欧拉计划.我相信这里的大多数人都已经看到或听说过这个问题，但为了完整起见，我将其放在这里:

So I'm doing Project Euler because dear gods do I need to practice writing code, and also my math skills are rusty as something very rusty. Thusly; Project Euler. I'm sure most here have already seen or heard of the problem, but I'll put it here just for completeness:

13195 的质因数是 5、7、13 和 29.600851475143 的最大质因数是多少?

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

为此，我编写了两个函数:

For this, I've written two functions:

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 整除(不是质数).如果没有发生任何特殊情况，它会运行一般素性测试.

This just checks any fed number for primality. It's working as intended (as far as I know), but now that I've said that I grow unsure. Anyway, it checks for special cases first: 1 (never prime), 2 (prime) or if it's divisible by 2 (not prime). If none of the special cases happen, it runs a general primality test.

这是我的分解代码:

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)，但之后会循环并设置x = 7，这将使整个事物无限循环，因为答案是2*2*5*5.递归在这里有帮助吗?我试过了，但它并没有变得更漂亮(对于某些数字，它仍然会进入无限循环).我现在不确定如何解决这个问题.

And this is definitely not working as intended. It is, sadly, working for the particular value of the Project Euler problem, but it doesn't work for, say, 100. I'm unsure what I need to do to fix this: what happens is that if it's a number like 100, it will correctly find the first 5 (2*2*5), but after that will loop around and set x = 7, which will make the entire thing loop infinitely because the answer is 2*2*5*5. Would recursion help here? I tried it, but it didn't get any prettier (it would still go into an endless loop for some numbers). I'm unsure how to solve this now.

推荐答案

您进展顺利，但需要考虑重复因素的可能性.你可以这样做:

You're on a good track, but you need to take account of the possibility of repeating factors. You can do that with something like this:

factors = []

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

这里的想法是您将继续将 2 添加到因子列表中，直到您测试的数字变为奇数.您也可以对其他因子使用类似的逻辑来增强分解方法.

The idea here being that you're going to continue adding 2's to the factor list until the number you're testing becomes odd. You can use similar logic for other factors as well to enhance your factorization method.

这篇关于Project Euler #3，因式分解的无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！