Python中的Project Euler#3

Question

供参考：

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

所以，经过一番努力，我解决了Euler项目的第三个问题。凯斯雷特的密码基本上不起作用。在

import math
import itertools

def is_prime(x):
    # Checks if the factor is prime. If not, breaks and looks at the next one
    split_tuple = math.modf(math.sqrt(x))
    max_prime_div_possible = int(split_tuple[1])
    prime = True
    for i in range(2, max_prime_div_possible+1):
        if x % i == 0:
            prime = False
            break
        else:
            pass
    return prime

def factor_me(x):
    # Creates a list of all factors of a number
    factors = []
    split_tuple = math.modf(math.sqrt(x))
    max_pf_possible = int(split_tuple[1])
    for i in xrange(2, max_pf_possible+1):
        if x % i == 0:
            factors.append(i)
            x = x/i
        else:
            pass

    # Checks each factor for prime-ity, and if it is, sets it as the max prime factor.
    for j in factors:
        if is_prime(j) == True:
            max_prime_factor = j
        else:
            pass
    return max_prime_factor


print factor_me(600851475143) # works correctly
print factor_me(6008514751435) # fails

问题是，即使代码在示例测试和提出的问题中都能正常工作，但是如果在要分解的数字上再加上一个数字，代码就会中断。举例说明一下，以6008514751435为例。
根据Wolfram Alpha，这一因素分为5、7和171671850041。然而，根据我的代码，最大的因子是7。所以，好吧，我被难住了。有什么建议吗？在

Answer 1

您只检查原始数字（6008514751435）的平方根（2451227）的系数。因为最后一个因子大于这个（171671850041），所以它永远不会加到factors。当循环排气时，x中剩下的东西，如果不是{}，则是最后的因素。您也可以停止检查一次x等于1。在

for i in xrange(2, max_pf_possible+1):
    if x % i == 0:
        factors.append(i)
        x = x/i
        if x == 1: break # Check that all factors found.
else:
    factors.append(x)

如果您对for/else不熟悉，else只在for循环耗尽时执行。^循环中的{}将跳过else。在