python - 寻找最大的除数(可能最快的程序)

我正在检查http://projecteuler.net/上的问题

第三个问题如下：


  13195的主要因素是5、7、13和29。最大的是什么
  数的素数600851475143？


我的解决方案代码如下。但它是如此之慢，以至于我认为将需要数周才能完成。
我该如何改善？还是Python本身太慢而无法解决此问题？

def IsPrime(num):
    if num < 2:
        return False
    if num == 2:
        return True
    else:
        for div in range(2,num):
            if num % div == 0:
                return False
        return True

GetInput = int (input ("Enter the number: "))


PrimeDivisors = []

for i in range(GetInput, 1, -1):
    print(i)
    if GetInput % i == 0 and IsPrime(i) is True:
        PrimeDivisors.append(i)
        break
    else:
        continue


print(PrimeDivisors)
print("The greatest prime divisor is:", max(PrimeDivisors))

最佳答案

解决方案的问题在于，您没有考虑到发现的主要因素，因此在您真正找到最大因素之后就不必检查这些因素。这是我的解决方案：

def largest_prime_factor(n):
    largest = None

    for i in range(2, n):
        while n % i == 0:
            largest = i
            n //= i

        if n == 1:
            return largest

    if n > 1:
        return n

欧拉计画的问题更多是数学问题，而不是程式设计问题，因此，如果您的解决方案速度太慢，可能不是您的语言出了问题。

请注意，我的解决方案偶然会针对此特定数字快速运行，因此绝对不是一般的解决方案。在此特定情况下，更快的解决方案are complicated和过大的杀伤力。

关于python - 寻找最大的除数(可能最快的程序)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20581491/