Перебор: делители и простые числа — практикум

10 класс, углублённый уровень. Занятие шестое: цикл по переменной и чем он отличается от цикла с условием, делители и простые числа, перебор отрезка — форма задания 25 ЕГЭ.

Часть 1. Тренажёр: что напечатает Python

Шесть типов задач, по одной на каждый. Считать в уме или на бумаге: запустив программу, вы узнаете ответ, но не научитесь. Ответ — ровно то, что появится на экране; если программа печатает несколько строк, перечисли их через пробел. Последний тип — задание 25 ЕГЭ в уме: там кода нет вовсе, числа перебираем в голове, отрезок для этого подобран короткий.

Часть 2. Как перебирают

Цикл по переменной: range

range(a, b) даёт числа от a до b − 1. Чтобы дойти до самого n, пишут range(1, n + 1) — это самая частая правка в задачах про делители. После цикла переменная хранит последнее пройденное значение.

for или while — одно и то же?

Любой for переписывается через while, и наоборот. Разница в удобстве: for берут, когда число шагов известно заранее («перебрать делители от 1 до n»), while — когда его определяет сама задача («пока делится», «пока не нашли»). Два отличия, из которых растут ошибки:

• после while в переменной остаётся первое неподошедшее значение, после for — последнее пройденное;
• менять переменную внутри for бесполезно: на следующем проходе range выдаст очередное значение. В while такая строка сдвинула бы все шаги.

Делители: перебор от 1 до n

Тот же цикл со s = s + d даёт сумму делителей, с print(d) — их список, с m = d — наибольший (максимум накоплением: последний найденный и есть наибольший). Делители ходят парами: если d делит n, то и n // d делит. Один из пары не больше корня из n — отсюда все быстрые проверки.

Простое число

Простое — то, у которого ровно два делителя: 1 и само число. Поэтому 1 — не простое (у него один делитель), а 2 — простое, и единственное чётное.

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

Разложение на множители

Здесь шаг делает не счётчик, а само число: 60 → 30 → 15 → 5 → 1. Пока n делится на d, снимаем d снова и снова: 64 даст шесть двоек. Составным d не окажется никогда: все его простые множители к тому моменту уже сняты.

Перебор отрезка: задание 25 ЕГЭ

В задании 25 дан отрезок или начало перебора и свойство: «числа, у которых ровно шесть делителей», «произведение двух простых», «делители с такой-то цифрой». Надо перебрать числа по порядку, для каждого проверить свойство и напечатать подходящие вместе с чем-то ещё — обычно с делителем. Это два вложенных цикла: внешний по отрезку, внутренний по делителям. Ниже — схема для первого из этих свойств: ровно шесть делителей.

Часть 3. Три программы

• Сохраняй решения в свою папку под именами zadanie1.py, zadanie2.py, zadanie3.py.
• Никаких приглашений в input(). Пиши input(), а не input("Введите число: ") — вывод читает машина.
• Выводи ровно то, что просят: те же слова, тот же порядок строк.
• Списков не нужно нигде: числа копятся в строке так же, как траектория исполнителя в прошлый раз.

28

Делители: 1 2 4 7 14 28
Количество: 6
Простое: нет

360

Множители: 2 2 2 3 3 5
Количество: 6
Наибольший: 5

95
100
6

98 49
99 33
Найдено: 2

Часть 4. Сдача

1. Файлы zadanie1.py … zadanie3.py лежат в твоей папке, отладочные print из них убраны.
2. В общей папке двойной щелчок по Проверка.bat.
3. «Найти мои файлы» → «Проверить всё».
4. Покажи учителю два экрана: тренажёр наверху этой страницы и итог оболочки.

Оболочка показывает, на каких данных программа ошиблась и что должна была вывести. Это подсказка: исправляй и проверяй снова, попыток сколько угодно.