Наибольший простой делитель
Простые делители числа 13195 - это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?
Оба числа из условия выглядят слишком большими (по крайней мере, для меня), поэтому смасштабируем задачу до чисел из первой двадцатки.
Давайте разберёмся, как найти такой делитель, например, для числа 6. Попробуем перебрать числа от 1 до 6 включительно. Если условное число делится на какое-то из них без остатка, запоминаем этот делитель и идём дальше.
number = 6
for i in range(1, number+1): # Поставим верхнюю границу
# равной данному числу
# На случай, если оно простое
if number % i == 0: # А ещё можно было написать “if not number % i”,
# потому что python принимает ноль,
# пустую строку, пустой список, словарь и т. д.,
# в качестве False, а любое не пустое
# (или не нулевое) значение – в качестве True
answer = i
number //= i
print(answer)
Работает для всех чисел от 1 до 7, а вот на 8 выдаёт неправильный ответ: 4 (явно не простое число). Посмотрим, почему так вышло. Восьмёрка делится на 2. Алгоритм учитывает это, делит её на 2 и идёт дальше. Однако он не учитывает, что 8 трижды делится на 2, он проверяет только один раз. Поэтому давайте заменим if на while.
Теперь код стал бесконечно зацикливаться при запуске. Это происходит из-за того, что перебор делителей начинается с 1. Код пытается посчитать, когда же данное число перестанет делится на единицу. Логично, что это у него не особо получится. Поэтому просто переправим 1 на 2 внутри range().
Меняем и это, теперь работает. Но подозрительно долго. В этот раз происходит косяк из-за того, что алгоритм продолжает перебирать числа даже когда они начинают превышать то, которое получилось из исходного при делении. Ну и ладно, поменяем конструкцию if на while и добавим условие, чтоб перебор заканчивался вовремя.
Итоговый код:
number = 600851475143
i = 2
while i <= number:
while number % i == 0:
answer = i
number //= i
i += 1
print(answer)
# Output: 6857
P. S. Если засунем в качестве исходного числа 6857, то сможем убедиться, что оно простое.