Задание 25: работа с делителями числа

На первый взгляд задание 25 выглядит как «найди делители — что тут сложного». Ловушка в том, что это вложенная задача: сначала вы перебираете числа в большом диапазоне (внешний цикл), а для каждого такого числа отдельно ищете его собственные делители (внутренний цикл). Именно эта вложенность — алгоритмический стержень всего задания, и именно на ней теряют баллы: одни забывают, что делитель нужно искать заново для каждого числа, другие не учитывают пары делителей и пропускают половину ответа.

Делитель числа n — это натуральное число, на которое n делится без остатка. У любого n есть как минимум два «скучных» делителя — 1 и само n. Их обычно исключают из подсчёта, и оставшиеся называют нетривиальными делителями (иногда — «собственными»). Именно нетривиальные делители чаще всего и являются предметом задания: посчитать их количество, сумму, найти наибольший или наименьший.

Что нужно знать

Как искать делители числа

Самый прямой способ — перебрать все числа от 2 до n−1 и проверить остаток от деления. Но для задания 25 диапазоны чисел доходят до сотен тысяч, и такой перебор для каждого числа работать будет слишком долго. Разумный приём — искать делители только до √n: если d делит n, то n/d — тоже делитель, и один из пары d, n/d обязательно не больше √n. Найдя d, сразу получаете второго «напарника» n/d — это удваивает найденные делители почти бесплатно.

Нетривиальные делители и типичные ловушки

Когда из рассмотрения убирают 1 и n, легко ошибиться со счётом на числах особой структуры. Например, число 125 = 5³ имеет всего делители 1, 5, 25, 125 — то есть два нетривиальных делителя (5 и 25), а не три и не один, как иногда предполагают по интуиции. Ещё коварнее числа вида p⁴ (четвёртая степень простого): у них ровно 5 делителей всего (1, p, p², p³, p⁴) и ровно 3 нетривиальных — это реальное условие из практики 4ege.ru («ровно три различных натуральных делителя, не считая 1 и самого числа»), и разбор такого случая — ниже.

Правило, которое стоит держать перед глазами: для числа n = p^k (степень одного простого числа) количество всех делителей равно k+1, а нетривиальных — k−1. Это не совпадение, а прямое следствие формулы количества делителей через разложение на простые множители.

Самая частая причина неверного ответа — забыть, что при d*d == n делитель d нужно добавить в список только один раз, иначе он задвоится и собьёт весь подсчёт «ровно N делителей».

Все делители vs нетривиальные делители

На практике встречаются варианты условия: считать делители, у которых чётность («не менее 120 чётных делителей»), которые сами являются простыми числами («хотя бы 6 различных простых делителей»), которые являются кубами нечётных чисел, или же оперировать суммой всех нетривиальных делителей («сумма больше 460000»). Логика поиска везде одна и та же — меняется только фильтр внутри внутреннего цикла.

Разбор примера

Рассмотрим упрощённый, но реалистичный вариант условия в духе практики 4ege.ru (задание 25.1, диапазон [81234; 134689], «ровно три различных натуральных делителя, не считая 1 и самого числа»).

Условие: Среди целых чисел из диапазона [80000; 90000] найдите число, у которого ровно три различных нетривиальных делителя (не считая 1 и самого числа). Для найденного числа выведите сами эти три делителя.

Рассуждаем так: три нетривиальных делителя — значит всего у числа 1 + 3 + 1 = 5 делителей. Число делителей 5 (простое) получается только у чисел вида p⁴, где p — простое (по формуле «количество делителей = k+1» для n = p^k, k+1=5 даёт k=4). Значит нужно искать в диапазоне четвёртую степень какого-то простого числа.

Показать решение и ответ

Проверяем степени простых чисел рядом с диапазоном [80000; 90000]:

• 16⁴ = 65536 — не подходит (16 не простое, и вне диапазона)
• 17⁴ = 83521 — попадает в диапазон, 17 простое ✓
• 18⁴ = 104976 — вне диапазона

Проверяем делители числа 83521 напрямую: 83521 = 17⁴. Его делители — 1, 17, 289 (17²), 4913 (17³), 83521. Нетривиальных (без 1 и без самого числа) ровно три: 17, 289, 4913.

Ответ: число 83521; нетривиальные делители — 17, 289, 4913.

Как решить в Python

# Внешний цикл — перебираем все числа диапазона
# Внутренний цикл — для КАЖДОГО числа ищем его собственные делители до корня

start, end = 80000, 90000
found = []

for n in range(start, end + 1):          # внешний цикл: кандидаты
    divisors = set()                     # сюда соберём нетривиальные делители n
    d = 2
    while d * d <= n:                    # внутренний цикл: ищем делители до √n
        if n % d == 0:
            divisors.add(d)              # сам делитель d
            divisors.add(n // d)         # его "напарник" n // d
        d += 1

    if len(divisors) == 3:               # условие: ровно три нетривиальных делителя
        found.append((n, sorted(divisors)))

for n, divs in found:
    print(n, divs)
# Ожидаемый вывод: 83521 [17, 289, 4913]

Обратите внимание на divisors.add(d) и divisors.add(n // d) — это и есть тот самый «двойной сбор» делителя и его пары, который экономит время перебора. Использование set вместо списка автоматически убирает дублирование, когда d * d == n (случай точного квадрата корня).

Как решить в Excel

Полноценный перебор до сотен тысяч строк в Excel неудобен, но для учебной демонстрации логики подойдёт ограниченный диапазон кандидатов-делителей.

1. В столбец A выпишите числа диапазона (например, 80000…90000) — это аналог внешнего цикла.
2. В отдельной области (например, строка 1, столбцы C:Z) выпишите кандидатов-делителей от 2 до 300 (это ≈ √90000) — фиксированный набор «предполагаемых» делителей.
3. На пересечении строки числа n и столбца делителя d поставьте формулу =ЕСЛИ(ОСТАТ($A2;C$1)=0;C$1;"") — она вернёт делитель, если он подходит, и пусто, если нет.
4. Количество нетривиальных делителей для числа n посчитайте формулой =СЧЁТЕСЛИ(C2:Z2;">0"), а сумму — =СУММ(C2:Z2) (если найденных делителей мало, для парного делителя n/d добавьте соседний блок столбцов с формулой =ЕСЛИ(ОСТАТ($A2;C$1)=0;$A2/C$1;""), чтобы не потерять «вторую половину» пар).
5. Отфильтруйте строки, где счётчик равен нужному значению (в нашем примере — 3), автофильтром или условным форматированием.

Это не заменит Python на реальном экзамене (там числа больше и диапазон делителей шире), но хорошо показывает саму механику «перебор кандидатов + проверка остатка», которая лежит в основе любого решения задания 25.