Делители парами

Что такое делитель и о каких делителях спрашивает условие?

d — делитель n, если n делится на d без остатка. Условие часто берёт не все делители: без единицы и самого числа, только чётные или только простые. Делители 12 — это 1, 2, 3, 4, 6 и 12: 12 = 1 · 12 = 2 · 6 = 3 · 4. А 5 не делитель: 12 = 5 · 2 + 2. Выбери требование — подходящие делители 12 выделятся:

все делители

12346121, 2, 3, 4, 6, 12

кроме 1 и самого числа

12346122, 3, 4, 6

чётные

12346122, 4, 6, 12

простые

12346122, 3простые числа разберём в подтеме 4

Единицу и само число исключают, только если условие говорит об этом прямо. Чётные делители 12 включают и само 12.

Как найти все делители числа, не проверяя каждое число до n? Для числа около миллиарда это миллиард проверок, а чисел в задаче — миллионы.

Делители идут парами: если d делит n, то и n // d делит n. Нашёл меньший делитель пары — получил и больший. Это хорошо видно на клетках: из 36 одинаковых клеток прямоугольник без пустых мест складывается пятью способами.

Ширина 4 подходит, потому что 36 делится на 4 — выходит ровно 9 рядов. Ширина 5 не подходит: 36 = 5 · 7 + 1, одна клетка лишняя. Ширина растёт — 1, 2, 3, 4, 6, — а высота падает — 36, 18, 12, 9, 6. На квадрате 6 × 6 они встречаются.

Дальше новых пар нет: ширина 9 — это тот же прямоугольник 4 × 9, только повёрнутый. Сторона квадрата из n клеток называется квадратным корнем из n, √n. Для 36 это 6.

Почему не бывает пары, в которой оба делителя больше √n?

Прямоугольник, у которого обе стороны больше 6, целиком накрывает квадрат 6 × 6 и ещё выходит за него — 36 клеток ему не хватит. Значит, в каждой паре хотя бы один делитель не больше √n.

Поэтому кандидатов d проверяют, только пока d · d ≤ n. Если n не квадрат, граница — целая часть корня: √40 между 6 и 7, и для 40 хватает d до 6. Её точно считает isqrt(n) из модуля math. Выигрыш огромный:

Как программа находит все девять делителей 36, проверив только числа от 1 до 6?

Для каждого d от 1 до √n: если n делится на d, в список идут d и его пара n // d. Пару квадрата 6 · 6 добавляют один раз. Слева на прямой — кандидаты от 1 до 6, справа — их пары. Переключай шаги: у каждого делителя появляется дуга к его паре, а не делитель отмечается крестиком.

Все дуги начинаются не правее пунктира √36. Большие делители 9, 12, 18 и 36 программа ни разу не проверяла — она получила их как пары. А на d = 6 пара — само 6, и добавлять его второй раз нельзя: у 36 девять различных делителей, а не десять.

Сам корень проверять обязательно: если для 49 остановиться перед 7, пропадёт делитель 7.

Делители понадобятся во многих задачах. Как написать поиск один раз и пользоваться им везде?

Оформить его функцией: она получает n и возвращает список его делителей по возрастанию. from math import isqrt подключает целый корень.

from math import isqrt def get_divisors(n):    divisors = []    for d in range(1, isqrt(n) + 1):        if n % d == 0:            divisors.append(d)            if n // d != d:                divisors.append(n // d)    return sorted(divisors) print(get_divisors(36))

isqrt(n) + 1 — потому что правая граница range не входит, а корень проверить надо. Делители находятся парами, и без sorted список был бы [1, 36, 2, 18, 3, 12, 4, 9, 6]. Функция возвращает список через return, а не печатает: дальше делители будем отбирать, считать и складывать. В следующих подтемах считаем, что она уже написана выше в программе.

Как оставить только те делители, о которых спрашивает условие?

Сначала найти все делители, потом отобрать нужные условием на делитель d. Отбор в одну строку записывает списковое включение: «d для каждого d из делителей, если 1 < d < n».

n = 36D = [d for d in get_divisors(n) if 1 < d < n]print(D)print(len(D), D[0], D[-1], sum(D))

Список отсортирован, поэтому наименьший делитель — D[0], наибольший — D[-1], второй по величине — D[-2]. Для других требований меняется только условие — выбери:

без 1 и n

1 < d < n

без самого числа

d < n

чётные

d % 2 == 0

оканчиваются на 7

d % 10 == 7

кратные 7

d % 7 == 0

Условие стоит на d, а не на n: d % 7 == 0 — «делитель кратен 7», а n % 7 == 0 — «само число кратно 7». И проверяй длину: если в списке один делитель, D[-2] вызовет ошибку.

Если нужно только количество делителей, зачем хранить их список?

Хватит счётчика: пара разных делителей добавляет 2, пара квадрата d · d = n — 1. count += 2 — это count = count + 2.

def count_divisors(n):    count = 0    for d in range(1, isqrt(n) + 1):        if n % d == 0:            if d * d == n:                count += 1            else:                count += 2    return count print(count_divisors(36), count_divisors(40))

У 36 пары 1 · 36, 2 · 18, 3 · 12 и 4 · 9 дают по два делителя, а 6 · 6 — один: 2 + 2 + 2 + 2 + 1 = 9. У 40 квадратной пары нет — четыре пары, восемь делителей.

• Делительn % d == 0
• Параd и n // d
• Границаd от 1 до isqrt(n) включительно
• Квадраткорень добавить один раз
• Отборусловие на d, а не на n; список — sorted
• Количество+2 за пару, +1 за корень