Условие задачи
Простые делители числа 13195 - это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?
Решение
Простым числом, является натуральное число больше единицы, которое имеет 2 делителя - 1 и само себя.
Для начала найдем все простые делители необходимого числа.
Чтобы сократить поиск будем перебирать до квадратного корня 600851475143 округленного вверх (функцией math.ceil)
Перебор будем вести начиная с числа 3.
Если i делит число на цело, рекурсивно обращаемся к функции issimple c аргументом i. Функция issimple возвращает пустой список если число является простым. В этом случае число попадает в результирующий список
Далее остается только вернуть максимальное значение массива простых чисел, которые нацело делят число 600851475143
Код Python
import math
def issimple(a):
r=math.ceil(math.sqrt(a))
lst=[]
for i in range(3,r):
if a%i==0:
if issimple(i)==[]:
lst.append(i)
return lst
r=issimple(600851475143)
print(max(r))
Данный алгоритм можно оптимизировать, введя дополнительные проверки на четность но для данной задачи все работает быстро