Информатика · ЕГЭ · 4 мин чтения

Как найти делители числа перебором на Python?

Редакция Алгоса · Обновлено

Короткий ответ

Для положительного целого n перебери кандидатов d от 1 до n включительно и проверь n % d == 0. Оператор % возвращает остаток от деления; нулевой остаток означает, что d является делителем. В Python верхняя граница range не включается, поэтому нужна запись range(1, n + 1). Начни с маленького числа и заранее выпиши ожидаемый результат.

Сначала составь список руками

Делитель положительного целого числа делит его без остатка. У 12 это 1, 2, 3, 4, 6, 12: например, 12 = 3 · 4. Число 5 не подходит, потому что 12 = 5 · 2 + 2. Здесь ищем положительные делители; дополнительные ограничения задачи, например исключение единицы, применяют отдельно.

Почему кандидат не может быть нулём?

Остаток вычисляется после деления на кандидата. Деление на ноль не определено, поэтому range начинает перебор с 1. Для положительного n кандидат больше n тоже не подойдёт: его положительное кратное уже больше самого n.

Каждая строка выполняет понятное действие

Цикл for повторяет вложенные команды для каждого кандидата. Условие if пропускает к выводу только подходящие значения. Отступ показывает, какая строка находится внутри цикла или проверки. Команда print печатает число; двойной знак == проверяет равенство, а одиночный = сохраняет значение под именем.

Рабочая программа и ответ
n = 12
for d in range(1, n + 1):
    if n % d == 0:
        print(d)

Вывод по строкам: 1, 2, 3, 4, 6, 12. Число 12 попало в перебор благодаря верхней границе n + 1.

Для больших чисел используй пары

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

  1. Проверь программу на n = 1 и на простом числе 7.
  2. Сравни вывод для n = 12 с ручным списком.
  3. Уточни, нужны все делители, их количество или только значения с дополнительным свойством.

Что запомнить

Нулевой остаток проверяет делимость. Границы перебора и условия отбора проверяй отдельно от скорости программы.

Попробовать на Алгосе

Программирование на Python для ЕГЭ

В теме «Делители и целые числа» начни с проверки условия делимости на маленьких числах.

Перейти к курсу Все курсы

Источники и материалы

Разобраться дальше

Все вопросы и разборы