Взятие навсегда: Проект Эйлера Задача 3 Python

Question

Я новичок. Мое решение ниже для Project Euler Задача № 3 требует вечного ответа. Кто-нибудь может предложить улучшение? Что я делаю неправильно? Я написал кусочки кодов, чтобы помочь мне вспомнить все кусочки головоломки проблемы.

Основными факторами 13195 являются 5, 7, 13 и 29.

Что такое Наибольший простой множитель числа 600851475143?

#limiter identification for iteration

def limiter(x):
    for i in range (2, x):
        if x % i == 0:
            return int (x/i)

#Prime checker 

def is_prime(a):
    for i in range (2, a):
        if a % i == 0:
            return False
    return True
#Lists all factors of a given no.

def factorlist(b):
    list = []
    for i in range (2, limiter(b)+1):
        if b % i == 0:
            list.append(i)
    return list

#Lists all prime factors of a given no.

def primefactor(p):
    plist = []
    for i in factorlist(p):
        if is_prime(i)== True:
            plist.append(i)

    return plist

print (primefactor(600851475143)[-1])

Answer 1

У меня нет ответа, но я скажу, что иногда операторы print () в функциях оказываются полезными для отладки в функциях. Пример, что ваша функция limiter () зависает на 71. Я обнаружил, что ваша программа работает на моем компьютере:

def limiter(x):
for i in range (2, x):
    print(i) <------------------ I added this
    if x % i == 0:
        return int (x/i)

Итак, добавление print () в ваши функции может помочь.

Answer 2

Рекурсивный подход к поиску наибольшего простого множителя будет проще и, вероятно, намного быстрее:

def lpf(N,p=2):                               # start from preceding prime factor
    for f in range(p,int(N**0.5)+1):          # factors up to square root
        if N%f==0 : return max(f,lpf(N//f,f)) # 1st prime vs lpf of counterpart
    return N # none found, N is prime itself

lpf(600851475143) # 6857