1. Идея

Нужно найти любой нетривиальный делитель числа n, то есть число d, для которого одновременно выполняется:

• d делит n,
• 1 < d < n.

Если такого делителя нет, нужно вывести -1.

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

Но перебирать все числа до n не нужно. Достаточно проверять делители только до sqrt(n).

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

Наблюдение 1

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

Почему так:

• пусть n = a * b;
• если оба числа a и b были бы больше sqrt(n), то их произведение было бы больше n, что невозможно;
• значит, хотя бы один из делителей не превосходит sqrt(n).

Поэтому достаточно искать делитель среди чисел от 2 до sqrt(n).

Наблюдение 2

Если в этом диапазоне делителя не нашлось, значит число либо:

• равно 1,
• либо простое.

В обоих случаях нет числа d, для которого 1 < d < n и d делит n. Значит, надо вывести -1.

Наблюдение 3

Первый найденный делитель точно подходит:

• он не равен 1, потому что перебор начинается с 2;
• он меньше n, потому что при d * d <= n и n > 1 такой d не может быть равен n.

3. Алгоритм

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

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

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

Случай 1: делитель найден

Если на некотором шаге найдено число d, такое что n % d == 0, то:

• d делит n,
• d >= 2, значит d > 1,
• так как перебор идёт только пока d * d <= n, имеем d <= sqrt(n), следовательно d < n для всех n > 1.

Значит, d — нетривиальный делитель, и его можно выводить.

Случай 2: делитель не найден

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

Значит, если в диапазоне до sqrt(n) делителей нет, то нет и нетривиального делителя вообще. Тогда правильный ответ — -1.

5. Сложность

Перебираются числа от 2 до sqrt(n).

• Время: O(sqrt(n))
• Память: O(1)

При n <= 10^12 это достаточно быстро.

6. Код на C++17

#include <iostream>
using namespace std;

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

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

    cout << -1 << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())

d = 2
while d * d <= n:
    if n % d == 0:
        print(d)
        break
    d += 1
else:
    print(-1)