Алгоритмы и структуры данных

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

Любое положительное число n ≥ 2 может быть представлено в виде произведения простых чисел:
Существует множество практических ситуаций, в которых необходимо найти простые делители числа. Например, определить количество делителей этого числа или лучше понять, как находятся наибольший общий делитель (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). Этот процесс продолжается, пока делитель не превысит . Если на каком-то шаге p становится больше , значит, оставшееся значение n само по себе является простым делителем, который тоже следует добавить к результату.
Таким образом, в нашем примере число 300 раскладывается на простые множители как .
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
  1. 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]
  1. p = 3, n = 3 ⇒ выходим из цикла while, так как p * p = 9, а 9 больше 2
  1. n > 1 ⇒ divisors = [2, 3], powers = [3, 1]
n = 75
  1. p = 2, n = 75
  1. p = 3, n = 75 n % 3 == 0 ⇒ divisors = [3], powers = [0] n //= 3 ⇒ n = 25, powers = [1]
  1. p = 4, n = 25
  1. 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]
  1. p * p > n ⇒ завершаем цикл while ⇒ divisors = [3, 5], powers = [1, 2]
n = 84
  1. p = 2, n = 84 n % 2 == 0 ⇒ divisors = [2], powers = [0] n //= 2 ⇒ n = 42, powers = [1] n //= 2 ⇒ n = 21, powers = [2]
  1. p = 3, n = 21 n % 3 == 0 ⇒ divisors = [2, 3], powers = [2, 0] n //= 3 ⇒ n = 7, powers = [2, 1]
  1. p * p > n ⇒ выходим из цикла while
  1. n > 1 ⇒ divisors = [2, 3, 7], powers = [2, 1, 1]
n = 31
  1. p = 2, n = 31
  1. p = 3, n = 31
  1. p = 4, n = 31
  1. p = 5, n = 31
  1. p = 6, n = 31
  1. p * p > n ⇒ выходим из цикла while
  1. n > 1 ⇒ divisors = [31], powers = [1]

Задача

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

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

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

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

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

Примеры

Input
Output
8
2
24
3
75
5
31
31
Бонус: Почему мы не проверяем только простые числа?
Текущая реализация алгоритма перебирает все числа 2, 3, 4, … вплоть до . Кажется, что логичнее было бы перебирать только простые числа?
На первый взгляд это вполне разумно (и есть задачи, где такой подход эффективен). Но чтобы сначала найти все простые числа до , нам потребуется больше операций, чем просто проверить деления на все числа до (если быть точнее, порядка ). То есть определение всех простых чисел до нужной границы может занять больше времени, чем непосредственный перебор всех возможных чисел и проверка деления на них.
Сможете ли вы придумать ситуацию, в которой имеет смысл сначала искать все простые числа, а только потом использовать их для определения простых делителей?
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue