Проверка на простоту для школьного номера

В школе каждому участнику кружка выдали «секретный номер» — одно целое число. Учитель сказал: если номер простой, то ученик проходит в команду на турнир.

Номер называют простым, если у него ровно два различных делителя: 1 и он сам.

Формат ввода

В одной строке записано целое число x.

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

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

Ограничения

• 2 ≤ x ≤ 1 000 000
• Время: 1 секунда, память: 256 МБ.

Пример

Ввод:

29

Вывод:

YES

Ключевое наблюдение: если число x составное, то у него есть делитель d, не превышающий sqrt(x). Почему так? Делители идут парами: если d * k = x и d > sqrt(x), то второй делитель k < sqrt(x). Значит, чтобы поймать составность, достаточно проверить только маленькие делители.

Это позволяет заменить «проверить все числа до x» на быстрый перебор до sqrt(x), что легко укладывается в ограничения до 1 000 000.

План решения:

• Считать x.
• Перебрать d от 2 до isqrt(x) включительно.
• Если x % d == 0, то найден нетривиальный делитель → вывести NO.
• Если перебор закончился без делителей → вывести YES.

Мини-сниппет условия проверки:

• if x % d == 0: ...

Сложность: O(sqrt(x)) по времени, для x = 1 000 000 это примерно 1000 проверок; память O(1).

Частая ошибка: неправильно выбрать границу цикла. Нужно проверять d до целого квадратного корня включительно (например, для x = 49 важно проверить d = 7), иначе квадраты простых могут ошибочно считаться простыми.