1. Идея

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

Ключевая мысль такая: если найти наименьший делитель d > 1, то число n / d и будет наибольшим собственным делителем.

Почему так? Потому что чем меньше делитель d, на который мы делим n, тем больше получается второй делитель n / d.

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

Наблюдение 1

Если d делит n, то вместе с ним существует парный делитель n / d.

Например, для n = 12:

• 2 и 6
• 3 и 4

Самый большой собственный делитель получается в паре с самым маленьким делителем больше 1.

Наблюдение 2

Если у числа n нет делителей от 2 до sqrt(n), значит оно простое.

Тогда его единственный собственный делитель — это 1.

Например:

• n = 13
• делителей кроме 1 и 13 нет
• ответ: 1

Наблюдение 3

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

Тогда ответом будет n / d, и искать дальше не нужно.

3. Алгоритм

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

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

Докажем, что алгоритм действительно находит наибольший собственный делитель.

Пусть первый найденный делитель d — это наименьший делитель числа n, который больше 1.

Тогда:

• d делит n
• значит существует парный делитель n / d

Теперь покажем, что n / d — максимальный собственный делитель.

Предположим, что существует собственный делитель x, который больше n / d.

Тогда парный ему делитель n / x будет меньше d.

Но n / x тоже должен быть делителем числа n, причём больше 1, потому что x < n.

Получаем противоречие: найден делитель меньше d, хотя d был минимальным.

Значит, большего собственного делителя, чем n / d, не существует.

Если же делителей от 2 до 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 << n / 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(n // d)
        break
    d += 1
else:
    print(1)