Задачи на программирование · делители до корня

Простое число

Задача составлена для базы знаний Grape — по мотивам типовых олимпиадных задач. Проверка — прямо на странице, как в автоматической проверяющей системе.

Как проверяет автоматическая система

  • Ответ — сама программа. Система запускает её на многих тестах: часть видна в условии, остальные скрыты.
  • На каждом тесте программа должна напечатать ровно ответ — без слов вроде «Ответ:».
  • Есть ограничение по времени: слишком медленная или зависшая программа тест не проходит.
  • Здесь так же: кнопка проверяет на всех тестах и останавливается на первой ошибке.

Условие

делители до корня

Число называется простым, если у него ровно два делителя: 1 и само число. Например, 7 — простое, а 9 — нет (делится на 3). Дано число N. Определи, простое ли оно.

Числа большие, поэтому перебирать все делители до N слишком долго — программа не уложится во время.

Входные данные. Одно целое число N (2 ≤ N ≤ 2·109).

Выходные данные. YES, если число простое, иначе NO.

Входные данныеВыходные данные
7YES
9NO
Твоя программа на Python
Разбор

Идея. Если у N есть делитель больше корня из N, то у него есть и пара — делитель меньше корня (36 = 4 · 9: 9 больше 6, а 4 меньше). Значит, проверять достаточно делители d, у которых d * d ≤ N. Для N = 2·109 это около 45 тысяч проверок вместо двух миллиардов.

Цикл закончился сам (без break) — делителей нет, и тогда d * d > n.

Решение на Python — комментарий после # объясняет строку, Python его не выполняет.

n = int(input())  # число
d = 2  # первый возможный делитель
while d * d <= n:  # делители ищем только до корня из n
    if n % d == 0:  # нашли делитель
        break  # дальше искать незачем
    d += 1  # пробуем следующий
print("YES" if d * d > n else "NO")  # дошли до корня без делителей — простое

Что используется в решении.

  • input() читает одну строку ввода, int() превращает её в целое число.
  • while условие: — цикл «пока»: повторяется, пока условие верно. Удобен, когда заранее неизвестно, сколько будет чисел, — например, до числа 0.
  • if условие: — ветвление: строки с отступом под ним выполняются, только если условие верно.
  • > — «больше».
  • += — увеличить переменную: count += 1 — то же, что count = count + 1.
  • print() — выводит ответ. Печатаем только ответ, без лишних слов.