Python 中的欧拉计划 #3

Question

供参考：

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

因此，经过相当多的修补，我解决了 Project 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 中剩余的任何内容，如果不是 1，则为最终因素。您也可以在 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 循环耗尽时执行。循环中的 break 将跳过 else.

Python 中的欧拉计划 #3

Project Euler #3 in Python

python

math

primes