1. Идея

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

По определению, простое число:

• больше 1;
• делится только на 1 и на само себя.

Самый прямой способ проверки: попробовать найти у n делитель среди чисел от 2 и дальше. Если хотя бы один делитель найден, число составное, иначе простое.

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

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

Наблюдение 1. Число 1 не является простым

Это прямо сказано в условии. Поэтому:

• если n <= 1, ответ сразу NO.

Наблюдение 2. Если у числа есть нетривиальный делитель, то один из делителей не больше sqrt(n)

Пусть число n составное. Тогда его можно представить как:

• n = a * b, где a > 1 и b > 1.

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

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

Отсюда следует:

• если среди чисел от 2 до sqrt(n) делителей нет, то больше их уже тоже не будет.

Наблюдение 3. Удобно проверять условие как i * i <= n

Чтобы не вычислять квадратный корень отдельно, можно идти циклом по i, пока выполняется:

• i * i <= n.

Это эквивалентно условию i <= sqrt(n) и хорошо работает в коде.

3. Алгоритм

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

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

Докажем корректность алгоритма.

Если алгоритм вывел NO

Это возможно в двух случаях:

• n <= 1. По определению такие числа не простые.
• найдено число i, такое что 2 <= i, i * i <= n и n % i == 0. Тогда у n есть делитель, отличный от 1 и самого n, значит число составное.

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

Если алгоритм вывел YES

Это значит:

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

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

Значит, число действительно простое, и ответ YES верный.

5. Сложность

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

• По времени: O(sqrt(n)), потому что проверяются все i от 2 до 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 <= 1) {
        cout << "NO";
        return 0;
    }

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

    cout << "YES";
    return 0;
}

7. Код на Python 3

n = int(input())

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

    if is_prime:
        print("YES")
    else:
        print("NO")