Условие
делители до корняЧисло называется простым, если у него ровно два делителя: 1 и само число. Например, 7 — простое, а 9 — нет (делится на 3). Дано число N. Определи, простое ли оно.
Числа большие, поэтому перебирать все делители до N слишком долго — программа не уложится во время.
Входные данные. Одно целое число N (2 ≤ N ≤ 2·109).
Выходные данные. YES, если число простое, иначе NO.
| Входные данные | Выходные данные |
|---|---|
| 7 | YES |
| 9 | NO |
Разбор
Идея. Если у 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()— выводит ответ. Печатаем только ответ, без лишних слов.