Цикл по переменной, делители и простые числа.
10 класс, углублённый уровень — занятие шестое.
Три урока плана за одну пару: for по range мы уже писали,
цифры числа доставали в прошлый раз. Новое сегодня одно, зато большое: перебор
как метод решения — и задание 25 ЕГЭ как его экзаменационная форма.
for i in range(5): # 0 1 2 3 4
for i in range(2, 6): # 2 3 4 5
for i in range(1, 10, 3): # 1 4 7
for i in range(10, 0, -2): # 10 8 6 4 2Начало, конец, шаг. Без начала — с нуля. Без шага — по единице. Правая граница не входит никогда.
range(5, 1) — пусто: начало больше конца, а шаг вперёд.
Идти вниз можно только отрицательным шагом.
n = 6
for d in range(1, n):
if n % d == 0:
print(d)Напечатает 1 2 3. Сама шестёрка потеряна.
n = 6
for d in range(1, n + 1):
if n % d == 0:
print(d)Напечатает 1 2 3 6.
Самая частая правка сегодняшней темы — + 1 в
range. И самая коварная: на 7 из 10 проверок разницы не видно.
for d in range(1, n + 1):
if n % d == 0:
print(d)«Перебрать всё от 1 до n».
d = 1
while d <= n:
if n % d == 0:
print(d)
d = d + 1Шаг делаем сами.
for; шаги считает задача («пока делится») —
while.
i = 1
while i < 10:
i = i + 1
print(i) 10Первое неподошедшее значение.
for i in range(1, 10):
s = i
print(i) 9Последнее пройденное.
for i in range(5):
i = i * 10 # бесполезно: range выдаст своё
print(i) 40Менять переменную внутри for нельзя — точнее, можно, но на
следующем проходе range всё равно выдаст очередное. В
while такая строка сдвинула бы шаги.
| Что ищем | Старт | В теле |
|---|---|---|
| сумма цифр | s = 0 | s = s + n % 10 |
| произведение | p = 1 | p = p * (n % 10) |
| минимальная цифра | m = 9 | if n % 10 < m: m = n % 10 |
| есть ли цифра 7 | f = "нет" | if n % 10 == 7: f = "да" |
while n > 0:
... # одна из строк таблицы
n = n // 10 # отрезать последнюю цифруПеребор как метод.
k = 0
for d in range(1, n + 1):
if n % d == 0:
k = k + 1
print(k) # сколько делителейТот же цикл со s = s + d — сумма, с print(d) — список,
с m = d — наибольший.
У 36 пара 6 · 6 схлопнулась в один делитель — у точного квадрата делителей нечётное число: у 36 их девять, у 49 — три.
Ровно два делителя: 1 и само число.
prime = n > 1 # флаг ставится ОДИН раз, до цикла
d = 2
while d * d <= n:
if n % d == 0:
prime = False # в цикле флаг только сбивают
d = d + 1Проверка по количеству делителей ещё честнее: посчитали — ровно два — простое. Тогда единица отпадает сама собой.
for d in range(2, n):
if n % d == 0:
prime = False
else:
prime = TrueПоследний проход — d = n − 1, на него n не делится, и флаг
снова True. Любое число «простое».
prime = True
for d in range(2, n):
if n % d == 0:
prime = FalseФлаг ставят до цикла, в цикле только сбивают.
range(2, 1) пуст, флаг
никто не сбил — «простое». Единицу проверяют отдельно:
prime = n > 1.
d = 2
while n > 1:
if n % d == 0: # делится — снять множитель
print(d)
n = n // d # d НЕ двигаем: мог войти ещё раз
else:
d = d + 1# n = 60: 60 --2--> 30 --2--> 15 --3--> 5 --5--> 1Здесь шаг делает не счётчик, а само число — поэтому while.
Составным d не окажется: все его простые множители уже сняты.
Снимет двойку из 64 один раз и уйдёт дальше. Ровно эта ошибка ждёт вас во втором задании — оболочка подаст 64.
В демоварианте 2027: перебирать числа, большие заданного, в порядке возрастания и искать те, что являются произведением ровно двух простых множителей — с дополнительным условием на запись множителей. В ответ — первые пять найденных чисел и для каждого наименьший множитель.
Форма всегда одна: перебрать по порядку → проверить свойство → напечатать число и что-то рядом. Свойство почти всегда про делители.
Пример свойства попроще, чем в демоварианте: ровно шесть делителей. Форма та же — меняется только проверка.
for n in range(a, b + 1): # внешний: отрезок
k = 0
for d in range(1, n + 1): # внутренний: делители
if n % d == 0:
k = k + 1
if k == 6:
print(n)| Сколько делителей | Какие числа | Пример |
|---|---|---|
| ровно 2 | простые | 2, 3, 5, 7, 11 |
| ровно 3 | квадрат простого | 4, 9, 25, 49 |
| ровно 4 | p · q или p³ | 6, 10, 14, 15, 8, 27 |
| нечётное | точные квадраты | 1, 4, 9, 16, 25 |
Это не для заучивания, а чтобы проверять себя: если программа нашла «число с тремя делителями» и оно не квадрат — программа врёт. На ЕГЭ такая проверка стоит дороже, чем ещё один запуск.
Сколько умножений нужно, чтобы посчитать x16? Пятнадцать
подряд — или четыре, если возводить в квадрат: x² → x⁴ → x⁸ → x¹⁶.
r = 1
while n > 0:
if n % 2 == 1: # нечётная степень — снять одну x
r = r * x
x = x * x # дальше работаем с квадратом
n = n // 2Тот же приём «пока n > 0: смотрим n % 2, режем n // 2», что и в разборе числа на цифры, только цифры двоичные. В сегодняшний практикум это не входит — оставляем тем, кто закончит раньше.
| № | Программа | Ради чего |
|---|---|---|
| 1 | Делители: список, количество, простое ли число | for по range до n + 1, накопитель-строка |
| 2 | Множители: разложение на простые, количество, наибольший | while, где шаг делает само число; «пока делится» |
| 3 | Ровно k делителей: перебрать отрезок, напечатать число и его наибольший делитель | вложенные циклы — форма задания 25 ЕГЭ |
zadanie1.py, zadanie2.py, zadanie3.py.Проверка.bat → «Найти мои файлы» → «Проверить всё».input() быть не должно: input(), а не
input("Введите число: "). Вывод читает машина. Списков не нужно:
числа копятся в строке, как траектория в прошлый раз.
Отметка: три задания — «5», два — «4», одно — «3». Попыток сколько угодно, оболочка каждый раз показывает, на каких данных программа ошиблась.
Сначала тренажёр, потом три программы.
Домашнее задание — на странице «Домашнее задание»: шесть типов задач на чтение кода и перебор в уме, Python дома не нужен. В начале следующей пары — проверочная по этим же типам.