Дано натуральное число n>1. Выведите его наименьший делитель, отличный от 1. Решение оформите в виде функции MinDivisor(n). Алгоритм должен иметь сложность порядка корня квадратного из n.
Указание. Если у числа n нет делителя не превосходящего корня из n, то число n — простое и ответом будет само число n. А у всех составных чисел обязательно есть делители, отличные от единицы и не превосходящие корня из n.
Формат ввода:
Вводится натуральное число.
Формат вывода:
Выведите ответ на задачу.
from math import sqrt n = int(input()) def MinDivisor(n): i = 2 if i <= sqrt(n): while n % i != 0: i += 1 print(i) else: print(n) MinDivisor(n)
Вроде выводит правильные ответы при запуске, но при отправке на сайт пишет:
“Test 55
Time Limit Exceeded”
Пытался гуглить, даже нашёл пару решений отличных от моего. Но их сайт тоже не принимает…