Лекция Новое

1. Что такое делители

Перед тем как разбирать алгоритм, вспомним определение.

Делители числа — это все числа, на которые данное число делится без остатка.

Например, для числа 12 делителями будут:

1, 2, 3, 4, 6, 12

Это все числа, на которые 12 делится без остатка.

2. Базовый алгоритм (перебор)

Самый простой способ найти делители — перебрать все числа от 1 до x:

x = int(input())
divs = []

for i in range(1, x + 1):
    if x % i == 0:
        divs.append(i)

print(divs)

Как работает алгоритм:

перебираем все числа от 1 до x
проверяем делимость
если делится — добавляем в список

Проблема

Этот алгоритм очень медленный для больших чисел. Если число ≈ 1 000 000, и таких чисел ≈ 100 000, то сложность становится огромной → программа не успеет выполниться на экзамене.

3. Идея оптимизации

Рассмотрим число 24:

1 × 24
2 × 12
3 × 8
4 × 6

Замечание:

делители образуют пары
если нашли один делитель i , то второй автоматически равен x // i.

👉 Значит, достаточно искать только "маленькие" делители

4. Где граница?

Граница между маленькими и большими делителями — это xx:

Если мы перебрали все числа до корня, то:

все маленькие делители найдены
большие получаются автоматически

5. Оптимизированный алгоритм

def divisors(x):
    divs = []
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            divs.append(i)
            divs.append(x // i)
    return sorted(divs)

Что изменилось:

перебор идет до корня
добавляем сразу два делителя

6. Проблема квадратов

Рассмотрим число 36:

6×6=366×6=36

При таком подходе число 6 добавится два раза.

7. Решение — множество (set)

Используем множество, чтобы автоматически убрать дубликаты:

def divisors(x):
    divs = set()
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            divs.add(i)
            divs.add(x // i)
    return sorted(divs)

set автоматически убирает повторы
код становится проще и надёжнее

8. Использование функции

print(divisors(36))

Результат:

[1, 2, 3, 4, 6, 9, 12, 18, 36]

Можно также найти количество делителей:

len(divisors(36))

9. Итог

Оптимальный алгоритм поиска делителей для ЕГЭ:

def divisors(x):
    divs = set()
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            divs.add(i)
            divs.add(x // i)
    return sorted(divs)

✔ Работает быстро

✔ Подходит для задания 25 ЕГЭ

✔ Достаточен для всех экзаменационных задач

Несимметричные графы