N. Простая задача

Один из самых интересных видов чисел в математике — простые числа. Их объединяет то, что делятся они лишь на 1 и само себя. До сих пор их изучают учёные по всему миру. Также они применяются в вычислительной технике: с их помощью можно писать алгоритмы, чтобы шифровать данные. Давайте напишем программу, чтобы определять — простое перед нами число или нет.

Формат ввода

Вводится одно натуральное число.

Формат вывода:

Требуется вывести сообщение YES если число простое, иначе — NO.

Пример

Ввод

1

Вывод

NO

Ввод

67

Вывод

YES

Решение

Алгоритм нахождения простого числа достаточно прост.

Если число равно единице, то оно не простое.
в противном случае пробуем делить число на множители начиная от двух и пока не дойдем до самого числа. Если остаток от деления числа на такой делитель равен нулю, то это значит что число не простое.

Но на самом деле нет необходимости проверять абсолютно все числа из диапазона, например, достаточно легко прийти к выводу, что у числа не может быть делителя большего, чем само число делёное на два. Если подумать еще немного, то можно прийти к выводу, что у числа не может быть делителя большего чем корень из числа. Таким образом верхняя граница для проверки выглядит как корень из числа + 1. таким образом мы придумали алгоритм перебора делителей. Это не самый эффективный алгоритм, но для наших целей и уровня владения языком, это самый подходящий алгоритм.

Обратите внимание, что нам снова потребуется флаг, чтобы обозначить ситуацию получилось ли разделить число нацело, пока мы перебирали делители.

num = int(input())

divisor = 2
prime = True

if num <= 1:
    prime = False
else:
    for divider in range(2, int(num**0.5 + 1)):
        if num % divider == 0:
            prime = False
            break

if prime is True:
    print('YES')
else:
    print('NO')

num = int(input())

divisor = 2
prime = True

if -1 <= num <= 1:
    prime = False
else:
    while divisor ** 2 <= num and prime is True:
        if num % divisor == 0:
            prime = False
        else:
            divisor = divisor + 1

if prime is True:
    print('YES')
else:
    print('NO')