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

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

Число называется простым, если делится только на \(1\) и на само себя. Определите, простое ли \(n\).

Входные данные

Одно целое число \(n\) (\(2 \le n \le 10^9\)).

Выходные данные

YES, если \(n\) простое, иначе NO.

Пример

Вход:

7

Выход:

YES

Ключевое наблюдение: если у составного числа n есть делитель d > 1, то второй делитель равен n / d. В паре один из них обязательно не больше sqrt(n). Значит, чтобы понять, простое ли n, не нужно перебирать все числа до n — достаточно проверить делители только до квадратного корня.

Почему это работает: если бы все делители были больше sqrt(n), то их произведение было бы больше n, что невозможно для пары делителей одного числа.

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

• Если n == 2, сразу ответ YES.
• Если n чётное (n % 2 == 0), то это не простое (для n > 2) → NO.
• Перебирать нечётные i от 3 и дальше, пока i * i <= n.
• Если нашёлся i, такой что n % i == 0, значит n составное → NO.
• Если цикл закончился без делителя, значит n простое → YES.

Мини-сниппет условия остановки: while i * i <= n: — так надёжнее, чем брать sqrt через float.

Сложность: O(sqrt(n)) проверок, для n до 1e9 это примерно до 31623, быстро.

Частая ошибка: забыть отдельный случай n = 2 или использовать int(n**0.5) и получить пограничную ошибку из-за округления.