Минимальный простой делитель

Question

Задача: "Дано целое число, не меньшее 2. Выведите его наименьший простой делитель." (1 не проходит, если что)

Если через Python проверить, то всё будет работать молниеносно при любых значениях, но Сириус всё равно выдаёт ошибку "Программа выполнялась слишком долго и была прервана". В чём проблема?

n = int(input())
i = 2

if n % 2 == 0:
    i = 2
else:
    while n % i != 0:
        i += 1
print(i)

Answer 1

Ну и если взять число Мерсенна ну или вообще любое простое число побольше ваш код будет очень долго работать, потому что он неэффективен

например возьмем число 1001 (простое), ваш код должен будет сделать 1001 проверку, хотя достаточно сделать 15 проверок

сложность вашего алгоритма O(n), а должна быть O(sqrt(n))

вот что вам надо будет сделать для нечетных n:

идти с шагом 2, а не с шагом 1 - это уменьшит кол-во рассматриваемых множителей в 2 раза (четные вам же не нужны)
проверять надо от 3 до sqrt(n), а не до n - это даст максимальное ускорение вашего алгоритма (к примеру для чисел больше миллиона надо сделать всего тысячу проверок)

Answer 2

Хотя бы так, но лучше перебирать только простые числа.

n = int(input())
if n%2 == 0:
    print(2)
else:
    for i in range(3, int(n**.5)+1, 2):
        if n%i == 0:
            print(i)
            break

БЛОГ НА HUSL

Минимальный простой делитель

Ответы (2 шт):