Проект Эйлера # 3 в Python

Question

Для справки:

простые множители 13195 являются 5, 7, 13 и 29. Что является самым большим главным фактором числа 600851475143?

Таким образом, я решил третью проблему проекта Эйлера после справедливого размаха. Не самый изящный из кодов, но он в основном работает.

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.