Минимальный делитель
Достаточно искать делитель до квадратного корня.
Как к ней подойти
Разберитесь, как повторять действие, пока выполняется условие, и вовремя остановить цикл.
Цикл while продолжается, пока условие истинно. Продумайте, какое значение меняется на каждом шаге и почему цикл когда-нибудь завершится. Проверяйте как обычный ввод, так и случай, когда тело цикла выполняется ноль раз.
У составного числа хотя бы один делитель не превосходит √n. Если такой не найден, число простое.
Проверьте перед запуском
- Единицу нельзя считать ответом; для простого числа ответ — само число.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Проверка до корня
У составного числа хотя бы один делитель не превосходит √n. Если такой не найден, число простое.
n = int(input())
d = 2
while d * d <= n and n % d != 0:
d += 1
print(d if d * d <= n else n)
Время: O(√n). Память: O(1).
Другой способ: Прямой перебор
Само n обязательно делитель; первый найденный делитель минимален. Метод проще, но медленнее на простых числах.
n = int(input())
d = 2
while n % d != 0:
d += 1
print(d)
Время: O(n). Память: O(1).