Задание 25. Информатика. ЕГЭ. Поляков-6997

Python

PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

def find_hcn(lim):
    hcn_candidates = []

    def generate_choices(index, curr, curr_divs, last_p):
        """
        Рекурсивная функция для подбора степеней простых чисел.
        index: индекс простого числа из списка PRIMES
        curr: текущее значение числа
        curr_divs: количество делителей текущего числа
        last_p: показатель степени предыдущего простого числа (для соблюдения a_i >= a_{i+1})
        """
        # Добавляем текущее число в список кандидатов
        hcn_candidates.append((curr, curr_divs))

        # Берем следующее простое число
        if index >= len(PRIMES):
            return

        p = PRIMES[index]
        # Пытаемся возвести текущее простое число в степень e
        # e не может быть больше степени предыдущего простого числа
        for e in range(1, last_p + 1):
            new_n = curr * (p ** e)
            if new_n > lim:
                break

            # Количество делителей для n = p1^a1 * p2^a2... вычисляется как (a1+1)*(a2+1)...
            new_divs = curr_divs * (e + 1)
            generate_choices(index + 1, new_n, new_divs, e)

    # Запускаем рекурсию: начинаем с числа 1, у которого 1 делитель,
    # максимальная возможная степень ограничена логарифмом (60 для двойки)
    generate_choices(0, 1, 1, 60)

    # Сортируем кандидатов по значению числа
    hcn_candidates.sort()

    # Отбираем только те числа, которые действительно являются "антипростыми"
    # (количество делителей строго больше, чем у любого меньшего числа)
    final_hcn = []
    max_divs = -1

    for n, divisors in hcn_candidates:
        if divisors > max_divs:
            final_hcn.append((n, divisors))
            max_divs = divisors

    return final_hcn

result = find_hcn(10**11)

for n, divs in result[-5:]:
    print(n, divs)

Ответ:
\(48886437600 \,\, 3456\)
\(64250746560 \,\, 3584\)
\(73329656400 \,\, 3600\)
\(80313433200 \,\, 3840\)
\(97772875200 \,\, 4032\)