Задачи с циклами: алгоритмы на числах

Всё, что нужно для темы урока, у нас уже есть – операция % из урока 1.6, которая в уроке 4.3 отделяла последнюю цифру числа. Здесь она работает в другой роли:

Число a делится на число b нацело, если остаток от деления равен нулю: a % b == 0. В этом случае b называют делителем числа a.

Проверка делимости – это не отдельная функция и не библиотека, а одно сравнение: if a % b == 0:. Отсюда получаются все три алгоритма урока:

• Найти все делители – перебрать кандидатов и оставить те, на которых остаток нулевой.
• Проверить на простоту – узнать, есть ли у числа делители, кроме 1 и самого себя.
• Найти НОД двух чисел – найти наибольшее число, которое делит оба.

Первые два решаются перебором, третий – тоже, но у него есть решение красивее и старше на две тысячи лет.

Начнём с самого прямого: у числа n делители могут быть только среди чисел от 1 до n включительно – больше n ни одно число его не делит. Значит, кандидатов конечное количество, и все они известны заранее. Это тот самый случай «я знаю, сколько раз» из урока 4.4 – берём for и range(1, n + 1).

Не забудьте про + 1: правая граница в range() не входит, а само число n – всегда свой собственный делитель, и терять его нельзя.

Внутри цикла – две знакомые вещи и ни одной новой. if из третьего блока проверяет условие отбора, счётчик count работает как накопитель из урока 4.3: заводится до цикла, растёт внутри, на работу самого цикла не влияет.

Для n = 12 программа напечатает 1, 2, 3, 4, 6, 12 – шесть делителей за двенадцать итераций. Половина проверок оказалась впустую, и это важно: цикл проверяет всех кандидатов, даже когда ответ уже понятен.

Простое число – натуральное число больше 1, у которого ровно два делителя: 1 и оно само.

Составное число – натуральное число больше 1, у которого есть хотя бы один делитель, кроме 1 и самого себя.

Два случая, которые постоянно ломают программы:

• 1 – не простое и не составное. У единицы всего один делитель, а простому нужно ровно два. Это не придирка математиков: если бы 1 считалась простой, разложение числа на простые множители перестало бы быть единственным.
• 2 – простое, причём единственное чётное простое. Проверку «делится на 2 → составное» нужно писать аккуратно, иначе сама двойка окажется составной.

Определение переводится в алгоритм почти дословно: перебрать кандидатов от 2 до n - 1 и посмотреть, найдётся ли хоть один делитель. Границы именно такие: 1 и n делят число всегда, проверять их бессмысленно.

И вот здесь пригождается урок 4.5. Как только найден первый делитель, дальше искать нечего – число уже составное. Это break. А если цикл дошёл до конца и ни разу не прервался – делителей нет, число простое. Это else, тот самый, который правильнее читать как «если не было прерывания».

Отступы здесь стоит прочитать внимательно: else записан на одном уровне с for, а не с if внутри цикла. Это else цикла из урока 4.5, и относится он к циклу.

Отдельный if n < 2 в начале – не костыль, а прямое следствие определения: для 0, 1 и отрицательных чисел цикл range(2, n) окажется пустым, тело не выполнится ни разу, сработает else – и программа радостно сообщит, что единица простая. Пустой диапазон из урока 4.4 здесь даёт неверный ответ, а не ошибку, и потому особенно опасен.

Пройдите проверку числа 91 по шагам ниже. Следите за тем, на какой итерации срабатывает break и что происходит после него.

Проверка 91 заняла 6 итераций – быстро. А теперь то самое число из начала урока: 1 000 003. Оно простое, а значит break не сработает ни разу и цикл честно доберётся до конца – миллион итераций ради ответа «да».

При этом бо́льшая часть этой работы бессмысленна, и увидеть почему проще всего на делителях. Выпишем делители числа 36 парами – так, чтобы произведение в паре давало 36:

Делители идут парами, и в каждой паре один множитель меньше 6, а другой больше – потому что $6 = \sqrt{36}$. Иначе и быть не может: если бы оба множителя были больше корня, их произведение оказалось бы больше самого числа.

Это рассуждение не про 36. Возьмём любое n и любой его делитель d, кроме 1 и самого n. У делителя есть пара – число n // d, и вместе они дают в произведении n. Оба числа пары больше корня быть не могут: тогда и произведение вышло бы больше n. Значит, меньшее из пары корень не превосходит:

Если число n составное, у него обязательно найдётся делитель d, для которого $1 < d \le \sqrt{n}$.

Для перебора это значит вот что: дошли до корня и ни одного делителя не встретили – дальше искать нечего, число простое. Для 1 000 003 это тысяча итераций вместо миллиона.

Как записать «до корня» в цикле? Можно взять range(2, int(n ** 0.5) + 1), но у возведения в дробную степень есть неприятная особенность: результат получается вещественным, а вещественные числа хранятся приближённо (подробно – блок 5), и для больших чисел корень может «промахнуться» на единицу.

Надёжнее обойтись целыми числами и записать то же условие умножением: i * i <= n. Это ровно то же самое, что i <= √n, но без вещественной арифметики вообще. Число итераций при этом заранее неизвестно – известно только условие продолжения. Знакомая ситуация: берём while.

Здесь вернулась переменная-флаг is_prime, от которой в уроке 4.5 мы уходили. И это тот самый случай, когда флаг уместен: else есть и у while, но результат проверки нужен нам дальше по программе, а не только для одного сообщения. Заодно флаг аккуратно закрывает случай n < 2 – начальное значение n >= 2 сразу ложно для нуля, единицы и отрицательных чисел.

Сравним объём работы:

На составных числах разницы почти нет – break спасает оба варианта. А вот на простых, где перебор идёт до конца, выигрыш растёт вместе с числом. Величина «во сколько раз алгоритм быстрее» – не мелочь и не про красоту кода; в блоке 10 мы научимся оценивать её заранее, не запуская программу.

НОД(a, b) – наибольшее натуральное число, на которое делятся нацело оба числа a и b.

Перебором это решается почти так же, как поиск делителей: кандидат не может быть больше меньшего из чисел, значит перебираем от 1 до min(a, b) и запоминаем последнее число, которое подошло обоим.

Условие and – из урока 3.7: делителем должны быть оба числа сразу. Обратите внимание, что break здесь не поставить: делители идут по возрастанию, и подходящий делитель нужен последний, а не первый.

Для НОД(1071, 462) перебор сделает 462 итерации. Между тем существует способ уложиться в три шага, и он старше почти всего, что есть в этом курсе: алгоритм описан в «Началах» Евклида (книга VII, около 300 года до н. э.). Название закрепилось за Евклидом потому, что его текст – самая ранняя дошедшая до нас запись; сам приём был известен греческим математикам и раньше.

Идея строится на одном наблюдении: если число делит a и b, то оно делит и остаток от деления a на b. Проверим на наших числах: 1071 % 462 = 147, и 21 действительно делит и 1071, и 462, и 147.

Значит, у пары (1071, 462) и у пары (462, 147) общие делители одни и те же – а вместе с ними одинаков и наибольший из них. Пару можно заменить на другую, поменьше, не потеряв ответа. Повторяем замену, пока второе число не станет нулём: НОД(x, 0) = x, потому что на x делится и само x, и ноль.

Сколько замен понадобится – заранее неизвестно, известно только условие остановки «пока второе число не ноль». Значит, while.

Строка a, b = b, a % b делает две замены одновременно: сначала вычисляются оба значения справа, и только потом они записываются в переменные. Если разбить её на две обычные строки, вторая уже испортит результат – a к тому моменту изменится. Так что если писать по шагам, то через дополнительную переменную:

r = a % b
a = b
b = r

Почему цикл вообще заканчивается? Потому что остаток всегда строго меньше делителя: b уменьшается на каждой итерации, а уменьшаться бесконечно натуральное число не может. Три части цикла из урока 4.2 на месте, просто изменение здесь не «плюс единица», а замена пары.

Пройдите алгоритм по шагам ниже – трёх итераций хватит, чтобы от пары (1071, 462) добраться до ответа 21.