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

Question

Помогите, пожалуйста. Мне 14. Только начал изучать Python на платформе Сириус. Смог решить все остальные задачи из темы «while», кроме одной задачи, которая мне не позволяет пройти на следующие темы. Задача «Минимальный простой делитель числа».

Условие: Дано целое число, не меньшее 2. Выведите его наименьший простой делитель. Нельзя использовать дополнительные библиотеки (math и т.п.)!

Входные данные: Вводится целое положительное число N <= 2*10 в 9-ой степени.

Выходные данные: Выведите ответ на задачу.

Пытался решить, написав код с while, но мой ответ не засчитывается, по причине слишком долгого времени работы программы. Рекомендуют организовать цикл, перебирающий делители до корня из числа N: while i*i <= N:, но я не могу понять, как это сделать.

Мой код Python (выдаёт ошибку «Программа выполнялась слишком долго и была прервана» либо «Программа выдаёт ошибку в процессе выполнения»):

N = int(input())
i = 2

while i*i <= N:
    if N%i != 0:
        i += 1
print(i)

Не могу понять, в чём ошибка. Подскажите, пожалуйста.

Answer 1

Не совсем понял, зачем "i*i <= N"? Если после while сразу прописать неравенство остатка нулю, то все норм работает)

N = int(input())
i = 2
while N%i != 0:
    i += 1
print(i)

Answer 2

Я бы делал так:

def prime_f(n):
    if n%2 == 0: return 2
    i = 3
    while n%i != 0 and i*i <= n:
        i+= 2
    if i*i <= n: return i
    return n

N = int(input())

print(prime_f(N))

Проверяем 2 отдельно, потом только нечетные, и до корня из N - иначе N само по себе простое.

Answer 3

N = int(input())
s=1/2
a=N
b=int(N**s)
for i in range(2,b+1) :
        if N%i == 0:
                if a > i :
                        a=i
print(a)

Программа прошла проверку по времени на сириусе.

Answer 4

while N%i != 0 это проверка на простоту числа, все четные, кроме 2 -ки будут составными, а значит их надо дальше делить, пока не упрешься в простое число, делящее входное без остатка.

Answer 5

Python:

a = int(input())
b = a - 1
while a < 2:
    print('Number need to be more than "2"')
    a = int(input())
while a % b != 0:
    b = b - 1
if a % b == 0:
    b = a // b
    print(b)

Answer 6

У меня такой вариант, по времени проходит

import math

num = int(input())

i = 2

while(i <= math.sqrt(num)):
  if num % i == 0:
    print(i)
    break
  i += 1
else:
  print(num)

Answer 7

Единственный код из моих вариантов, который прошёл проверку по времени:

a = int(input())
b = 2
c = int(a**(1/2))

while a % b != 0 and b < c:
    b += 1

if a % b == 0:
    print(b)
else:
    print(a)

БЛОГ НА HUSL

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

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