4

Только начал изучать 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)

Не могу понять, в чём ошибка?

3
  • 1
    Ну как минимум отдельно пробуешь 2, 3 и 5, а потом только нечётные кроме делящихся на 5. Уже в 2.5 раза быстрее получится.
    – Akina
    Commented 17 апр. 2020 в 20:28
  • 5
    Надо завершать цикл как только нашли число. А сейчас как только вы нашли ответ вы перестаете увеличивать число i, а следовательно цикл становиться бесконечным ! И умножение i*i в проверке цикла это медленно. очень может статься что заранее вычисленное M=N/2 и while i <= M будет даже лучше, чем следование до корня, вычислением квадрата
    – Mike
    Commented 17 апр. 2020 в 22:14
  • n = int(input()) if n%2==0: i = 2 elif n%3==0: i = 3 elif n%4==0: i = 4 elif n%5==0: i = 5 else: i = n print(i) У меня тоже пишет, что неверный ответ. Не понимаю... Помогите.
    – Лев
    Commented 25 окт. 2021 в 9:45

6 ответов 6

5

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

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 само по себе простое.

0
1

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

N = int(input())
i = 2
while N%i != 0:
    i += 1
print(i)
2
  • 1
    А где проверка делителя на простоту?
    – MiniMax
    Commented 17 апр. 2020 в 23:41
  • 6
    @MiniMax Она не нужна - как вы представляете, что число делится на составное, но не делится на простое, есляющееся делителем составного? А вот к эффективности O(N) да еще и с полным перебором и правда вопросы...
    – Harry
    Commented 18 апр. 2020 в 5:22
1
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)

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

1
  • 1
    Один в один мое решение, просто замедленное в 2 раза :)
    – Harry
    Commented 9 мая 2020 в 10:57
0
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)
2
  • Вы тестировали свое решение на больших N? например на N=2000000000, как в условии задачи?
    – extrn
    Commented 25 авг. 2020 в 7:44
  • Точно! недосмотрел. Спасибо
    – user404236
    Commented 27 авг. 2020 в 7:40
0

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

import math

num = int(input())

i = 2

while(i <= math.sqrt(num)):
  if num % i == 0:
    print(i)
    break
  i += 1
else:
  print(num)
2
  • А в этой ветке ещё не было таких решений?
    – MBo
    Commented 9 сент. 2021 в 13:01
  • "Нельзя использовать дополнительные библиотеки (math и т.п.)!". Commented 31 июл. 2023 в 20:50
0

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

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)

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.