python - 寻找最大的质因数(最快的程序)

Question

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

第三个问题如下:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 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))

Answer 1

你的解决方案的问题是你没有考虑你找到的主要因素，所以你在你真正找到最大的因素之后不必要地检查因素。这是我的解决方案:

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并且在这种特定情况下矫枉过正。