Разложение на простые множители

Любое положительное число n ≥ 2 может быть представлено в виде произведения простых чисел:

\begin{aligned} 2 &= 2 &&= 2^1 \\ 4 &= 2 \cdot 2 &&= 2^2 \\ 49 &= 7 \cdot 7 &&= 7^2 \\ 24 &= 2 \cdot 2 \cdot 2 \cdot 3 &&= 2^3 \cdot 3^1 \\ 75 &= 3 \cdot 5 \cdot 5 &&= 3^1 \cdot 5^2 \\ 84 &= 2 \cdot 2 \cdot 3 \cdot 7 &&= 2^2 \cdot 3^1 \cdot 7^1 \end{aligned}

Существует множество практических ситуаций, в которых необходимо найти простые делители числа. Например, определить количество делителей этого числа или лучше понять, как находятся наибольший общий делитель (GCD) и наименьшее общее кратное (LCM) для двух чисел и т.д.

Чтобы представить число n (например, 300) в виде произведения простых множителей, можно начать с наименьшего простого числа p (2) и, если n делится на p, делить n на p столько раз, сколько это возможно (300 / 2 = 150, 150 / 2 = 75).

Затем увеличить p на 1 (p = 3) и попробовать поделить n на новое значение p. Если деление возможно, делим число n на p столько раз, сколько оно делится (75 / 3 = 25).

После этого снова увеличиваем p на 1 (p = 4) и пробуем делить n на 4. Однако мы уже «выбрали» все двойки до этого, поэтому оставшееся число больше не делится на 4 (ведь 4 — это 2×2). Аналогично, следующие числа, которые будут кратны уже использованным простым множителям, делителями не окажутся. При переходе от меньшего числа к большему мы гарантируем, что на каждом этапе сталкиваемся только с простыми делителями.

На следующем шаге увеличиваем делитель еще на 1 (p = 5) и пытаемся делить n (75 / 5 = 5, затем 5 / 5 = 1). Этот процесс продолжается, пока делитель не превысит $\sqrt{n}$ . Если на каком-то шаге p становится больше $\sqrt{n}$ , значит, оставшееся значение n само по себе является простым делителем, который тоже следует добавить к результату.

Таким образом, в нашем примере число 300 раскладывается на простые множители как $2 \cdot 2 \cdot 3 \cdot 5 \cdot 5$ .

n = ...                              # Представляем n в виде произведения простых множителей
p, divisors, powers = 1, [], []      # простой делитель, список делителей и их показатели

while p * p <= n:                    # пока p <= sqrt(n)
    p += 1                           # Увеличиваем простой делитель на 1 в каждой итерации
    if n % p != 0:                   # Если n не делится на p, ничего не делаем
        continue
    
    divisors.append(p)               # n % p == 0 => добавляем p как простой делитель
    powers.append(0)                 # начально показатель равен 0
    while n % p == 0:                # делим максимальное количество раз
        n //= p
        powers[-1] += 1              # увеличиваем показатель на 1 в каждой итерации

if n > 1:                            # если p > sqrt(n) => n само по себе простой делитель
    divisors.append(n)               # добавляем n как делитель
    powers.append(1)                 # с показателем 1

print(list(zip(divisors, powers)))   # выводим делители и их показатели вместе

На каждой итерации алгоритма мы, если возможно, делим число на найденный простой делитель и одновременно увеличиваем показатель этого делителя на 1.

Рассмотрим, как алгоритм работает на нескольких примерах:

n = 24

p = 2, n = 24 (в начале цикла мы увеличили p с 1 до 2)
n % 2 == 0 ⇒ divisors = [2], powers = [0]
n //= 2 ⇒ n = 12, powers = [1]
n //= 2 ⇒ n = 6, powers = [2]
n //= 2 ⇒ n = 3, powers = [3]
p = 3, n = 3 ⇒ выходим из цикла while, так как p * p = 9, а 9 больше 2
n > 1 ⇒ divisors = [2, 3], powers = [3, 1]

n = 75

p = 2, n = 75
p = 3, n = 75
n % 3 == 0 ⇒ divisors = [3], powers = [0]
n //= 3 ⇒ n = 25, powers = [1]
p = 4, n = 25
p = 5, n = 25
n % 5 == 0 ⇒ divisors = [3, 5], powers = [1, 0]
n //= 5 ⇒ n = 5, powers = [1, 1]
n //= 5 ⇒ n = 1, powers = [1, 2]
p * p > n ⇒ завершаем цикл while ⇒ divisors = [3, 5], powers = [1, 2]

n = 84

p = 2, n = 84
n % 2 == 0 ⇒ divisors = [2], powers = [0]
n //= 2 ⇒ n = 42, powers = [1]
n //= 2 ⇒ n = 21, powers = [2]
p = 3, n = 21
n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0]
n //= 3 ⇒ n = 7, powers = [2, 1]
p * p > n ⇒ выходим из цикла while
n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]

n = 31

p = 2, n = 31
p = 3, n = 31
p = 4, n = 31
p = 5, n = 31
p = 6, n = 31
p * p > n ⇒ выходим из цикла while
n > 1 ⇒ divisors = [31], powers = [1]

Задача

По заданному числу n требуется найти его наибольший простой делитель.

Входные данные

Первая строка содержит целое число n (2 ≤ n ≤ $10^9$ ).

Выходные данные

Программа должна вывести наибольший простой делитель числа n.

Примеры

Input	Output
8	2
24	3
75	5
31	31

Бонус: Почему мы не проверяем только простые числа?

Текущая реализация алгоритма перебирает все числа 2, 3, 4, … вплоть до $\sqrt{n}$ . Кажется, что логичнее было бы перебирать только простые числа?

На первый взгляд это вполне разумно (и есть задачи, где такой подход эффективен). Но чтобы сначала найти все простые числа до $\sqrt{n}$ , нам потребуется больше операций, чем просто проверить деления на все числа до $\sqrt{n}$ (если быть точнее, порядка $\mathcal{O}(\sqrt{n} \cdot \log \log \sqrt{n})$ ). То есть определение всех простых чисел до нужной границы может занять больше времени, чем непосредственный перебор всех возможных чисел и проверка деления на них.

Сможете ли вы придумать ситуацию, в которой имеет смысл сначала искать все простые числа, а только потом использовать их для определения простых делителей?

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB