3 Главный приём — рекурсивное разложение на простые множители

Главный приём — рекурсивное разложение на простые множители

Идея: находим наименьший делитель числа (перебором от 2 до √x). Он обязательно простой — будь у него делитель поменьше, тот делил бы и x. Записываем этот множитель и рекурсивно раскладываем то, что осталось (x // i). Если делитель не нашёлся — число само простое, возвращаем его.

def p(x):
    for i in range(2, int(x**0.5) + 1):   # ищем наименьший делитель до корня
        if x % i == 0:
            return [i] + p(x // i)         # i — простой; раскладываем остаток
    return [x]                             # делителей нет — x само простое

Функция возвращает список простых множителей по возрастанию. Например:

  • p(12) → [2, 2, 3] (12 = 2·2·3)

  • p(2726730289) → [67, 40697467] (произведение двух простых)

  • p(97) → [97] (само простое)

📌 Что даёт список множителей

Из списка d = p(x) сразу читается всё нужное: len(d) — сколько простых множителей (с учётом повторов); min(d) — наименьший простой делитель (это d[0]); max(d) — наибольший (это d[-1]); len(p(M)) == 1 — проверка, что число M простое. Одна функция закрывает весь номер.

Главный приём — рекурсивное разложение на простые множители — Задание | Методички — Профиматика