1. Идея

Нужно определить, является ли число n простым.

Простое число — это число, у которого ровно два различных делителя: 1 и само число.

Самый прямой способ — проверить, есть ли у n какой-нибудь делитель кроме 1 и n. Если такой делитель найден, число составное, ответ NO. Если не найден — число простое, ответ YES.

Но перебирать все числа от 2 до n - 1 слишком долго. Можно значительно ускориться: достаточно проверять делители только до sqrt(n).

2. Наблюдения

Наблюдение 1: числа меньше 2 не простые

Числа 0 и 1 не являются простыми, потому что у них нет ровно двух различных делителей.

Значит, если n < 2, сразу выводим NO.

Наблюдение 2: если у числа есть делитель, то один из них не больше sqrt(n)

Если число n составное, то его можно представить как n = a * b, где a > 1 и b > 1.

Предположим, что оба числа a и b больше sqrt(n). Тогда их произведение было бы больше n, что невозможно.

Значит, хотя бы один делитель обязательно не превосходит sqrt(n).

Отсюда следует важный вывод:

• если среди чисел от 2 до sqrt(n) нет делителей n,
• то у n вообще нет нетривиальных делителей,
• значит, n простое.

Наблюдение 3: удобно проверять условие через d * d <= n

Чтобы не вычислять корень отдельно, можно в цикле проверять условие d * d <= n.

Это эквивалентно проверке d <= sqrt(n) и хорошо работает для заданных ограничений.

3. Алгоритм

1. Считать число n.
2. Если n < 2, вывести NO.
3. Перебирать d от 2, пока d * d <= n:
   • если n % d == 0, то найден делитель, вывести NO и завершить программу.
4. Если цикл закончился и делителей не найдено, вывести YES.

4. Почему это работает

Рассмотрим два случая.

Случай 1: программа выводит NO

Это возможно в двух ситуациях:

• n < 2. Такие числа не являются простыми по определению.
• найдено число d от 2 до sqrt(n), для которого n % d == 0. Тогда d — делитель числа n, отличный от 1 и n, значит n составное.

В обоих случаях ответ NO правильный.

Случай 2: программа выводит YES

Это значит:

• n >= 2;
• среди всех чисел от 2 до sqrt(n) не нашлось ни одного делителя.

Предположим противное: пусть n составное. Тогда у него существует делитель d, такой что 2 <= d <= sqrt(n). Но программа проверила все такие d и не нашла ни одного. Противоречие.

Значит, n не составное. При n >= 2 это означает, что n простое.

Следовательно, программа всегда дает правильный ответ.

5. Сложность

Пусть n — входное число.

Цикл выполняется не более чем для всех d от 2 до sqrt(n).

• Время работы: O(sqrt(n))
• Используемая память: O(1)

При n <= 10^12 это достаточно эффективно: максимум около 10^6 проверок.

6. Код на C++17

#include <iostream>

using namespace std;

int main() {
    long long n;
    cin >> n;

    if (n < 2) {
        cout << "NO\n";
        return 0;
    }

    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    return 0;
}

7. Код на Python 3

n = int(input())

if n < 2:
    print("NO")
else:
    prime = True
    d = 2
    while d * d <= n:
        if n % d == 0:
            prime = False
            break
        d += 1
    if prime:
        print("YES")
    else:
        print("NO")