1. Идея

Нужно найти минимальное простое число, которое строго больше n.

Самый прямой способ:

• начать с числа n + 1;
• проверять по очереди числа n + 1, n + 2, n + 3, ...;
• как только встретили простое число — вывести его.

Значит, задача сводится к двум действиям:

1. уметь проверять, простое ли число;
2. перебирать числа вверх от n + 1, пока не найдём подходящее.

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

1. Как проверять число на простоту

Число x является простым, если у него нет делителей, кроме 1 и самого x.

Наивно можно было бы проверять все числа от 2 до x - 1, но это слишком долго.

Важно наблюдение:

• если у числа x есть делитель больше sqrt(x),
• то обязательно существует и парный делитель меньше sqrt(x).

Поэтому достаточно проверить делимость только до тех пор, пока d * d <= x.

2. Чётные числа можно почти сразу отсеять

• число 2 — простое;
• любое другое чётное число простым быть не может.

Значит:

• если x < 2, то оно не простое;
• если x == 2, то оно простое;
• если x чётное и больше 2, то оно составное.

После этого можно проверять только нечётные делители: 3, 5, 7, ....

3. Перебор следующего числа

После чтения n заводим cur = n + 1.

Пока cur не простое, увеличиваем его на 1.

Как только нашли простое — это и будет ответ, потому что мы шли строго по возрастанию.

3. Алгоритм

Проверка на простоту isPrime(x)

1. Если x < 2, вернуть false.
2. Если x == 2, вернуть true.
3. Если x чётное, вернуть false.
4. Перебирать нечётные делители d от 3, увеличивая на 2, пока d * d <= x:
   • если x % d == 0, вернуть false.
5. Если делитель не найден, вернуть true.

Основной алгоритм

1. Считать n.
2. Положить cur = n + 1.
3. Пока cur не простое:
   • увеличить cur на 1.
4. Вывести cur.

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

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

Корректность функции проверки на простоту

Функция isPrime(x) работает так:

• числа меньше 2 не являются простыми — это верно по определению;
• число 2 простое;
• любое чётное число больше 2 делится на 2, значит простым не является;
• для нечётного x остаётся проверить, есть ли у него нечётный делитель.

Почему достаточно проверять делители только до sqrt(x)?

Если x составное, то x = a * b, где a > 1 и b > 1. Если бы одновременно a > sqrt(x) и b > sqrt(x), то тогда a * b > x, что невозможно. Значит, хотя бы один из делителей не превосходит sqrt(x).

Следовательно:

• если среди чисел от 2 до sqrt(x) делителя нет, то x простое;
• если делитель найден, то x составное.

Функция isPrime(x) возвращает истину тогда и только тогда, когда x — простое число.

Корректность основного перебора

Мы начинаем с cur = n + 1, то есть с первого числа, которое строго больше n.

Далее по очереди рассматриваем все числа: n + 1, n + 2, n + 3, ...

Как только встречаем первое простое число, сразу останавливаемся и выводим его.

Так как:

• все числа больше n проверяются по порядку,
• первое найденное простое число и есть минимальное простое число, строго большее n,

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

5. Сложность

Пусть проверяемое число равно x.

• Проверка числа на простоту работает за O(sqrt(x)), потому что мы перебираем делители до sqrt(x).
• Основной алгоритм вызывает эту проверку для нескольких подряд идущих чисел, начиная с n + 1.

Итогово:

• время работы в худшем случае — O(k * sqrt(n)), где k — сколько чисел пришлось проверить до ближайшего следующего простого;
• память — O(1).

Для ограничений задачи этого достаточно.

6. Код на C++17

#include <iostream>

using namespace std;

bool isPrime(long long x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;

    for (long long d = 3; d * d <= x; d += 2) {
        if (x % d == 0) return false;
    }
    return true;
}

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

    long long cur = n + 1;
    while (!isPrime(cur)) {
        cur++;
    }

    cout << cur << '\n';
    return 0;
}

7. Код на Python 3

def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False

    d = 3
    while d * d <= x:
        if x % d == 0:
            return False
        d += 2
    return True

n = int(input())

cur = n + 1
while not is_prime(cur):
    cur += 1

print(cur)