1. Идея

Нужно найти такие натуральные числа a и b, что:

• a * b = n
• a <= b
• периметр 2 * (a + b) минимален

Так как множитель 2 на сравнение не влияет, достаточно минимизировать сумму a + b.

Из условия уже дана важная подсказка: минимальный периметр получается у той пары множителей, которая наиболее близка друг к другу. Значит, нужно искать делитель a, который как можно ближе к sqrt(n), но при этом делит n.

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

Наблюдение 1. Если a * b = n, то достаточно искать a <= sqrt(n)

Если a > sqrt(n), то второй множитель b = n / a будет меньше sqrt(n).
То есть любая пара множителей симметрична относительно sqrt(n).

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

Наблюдение 2. Чем ближе множители друг к другу, тем меньше их сумма

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

• 1 * 36, сумма 37
• 2 * 18, сумма 20
• 3 * 12, сумма 15
• 4 * 9, сумма 13
• 6 * 6, сумма 12

Видно, что чем ближе множители, тем меньше сумма, а значит и периметр.

Наблюдение 3. Достаточно идти вниз от sqrt(n)

Если взять целую часть sqrt(n) и двигаться вниз, то первый найденный делитель будет максимально близок к sqrt(n) слева.
Значит, именно он даст нужную пару с минимальным периметром.

3. Алгоритм

1. Считать число n.
2. Найти s = floor(sqrt(n)).
3. Из-за возможных ошибок округления аккуратно поправить s:
   • пока (s + 1) * (s + 1) <= n, увеличивать s
   • пока s * s > n, уменьшать s
4. Перебирать a от s вниз до 1.
5. Как только найдено число a, для которого n % a == 0, вывести:
   • a
   • n / a
6. Завершить программу.

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

Пусть a * b = n и a <= b.

Нужно выбрать такую пару, чтобы сумма a + b была минимальной.

Рассмотрим все делители a, не превосходящие sqrt(n). Для каждого такого a второй множитель равен b = n / a.

Если a увеличивается и остается не больше sqrt(n), то b уменьшается, а множители становятся ближе друг к другу. Именно в этой области сумма a + b уменьшается при приближении к sqrt(n).

Значит, лучшая пара — это та, где a является наибольшим делителем n, не превосходящим sqrt(n).

Алгоритм как раз и делает это:

• начинает с floor(sqrt(n))
• идет вниз
• находит первый делитель a

Первый найденный делитель — ближайший к sqrt(n) снизу, следовательно, пара (a, n / a) имеет минимальный периметр.

5. Сложность

Поиск идет от sqrt(n) вниз до первого делителя.

• В худшем случае число проверок — O(sqrt(n))
• Память — O(1)

При n <= 10^12 это подходит: sqrt(n) <= 10^6, что вполне допустимо.

6. Код на C++17

#include <iostream>
#include <cmath>

using namespace std;

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

    long long s = sqrt((long double)n);
    while ((s + 1) * (s + 1) <= n) s++;
    while (s * s > n) s--;

    for (long long a = s; a >= 1; a--) {
        if (n % a == 0) {
            cout << a << " " << (n / a) << "\n";
            break;
        }
    }

    return 0;
}

7. Код на Python 3

n = int(input())

s = int(n ** 0.5)
while (s + 1) * (s + 1) <= n:
    s += 1
while s * s > n:
    s -= 1

a = s
while a >= 1:
    if n % a == 0:
        print(a, n // a)
        break
    a -= 1