Обработка целых чисел

Начнём с целых чисел: это числа без дробной части, например −3, 0, 4 и 125. В задании обычно дан отрезок таких чисел, который нужно проверить по очереди.

В условии могут попросить проверить все целые числа от одного значения до другого. Например, на отрезке от 4 до 8 есть пять чисел: 4, 5, 6, 7 и 8. Слова «от ... до ... включительно» означают, что проверяются обе границы.

В Python для такого повтора используют range. Его правая граница не входит в перебор: запись range(4, 8) даёт 4, 5, 6 и 7. Поэтому, если нужно включить число 8, в правой границе указывают 9. Так устроен цикл for: он последовательно берёт значения диапазона и выполняет вложенные команды. Сам цикл подробно рассматривается в уроке мини-курса Python о цикле for и диапазоне.

Команда print выводит значение на экран. Поэтому сначала проверим сам диапазон без дополнительных условий: каждая строка покажет очередное число.

1for number in range(4, 9):2    print(number)  # по одному в строке: от 4 до 8

Если при делении одного целого числа на другое не остаётся «лишней» части, первое число делится на второе нацело. Например, 18 делится на 6, потому что 18 можно составить из трёх шестёрок. Число, которое делят, называют делимым, а число, на которое делят, — делителем.

Python находит остаток от деления с помощью знака %. Если остаток равен нулю, деление было нацело. Поэтому проверку «число делится на 6» записывают как number % 6 == 0. Знак сравнения == спрашивает, равны ли значения; один знак = присваивает значение переменной. Арифметические знаки Python, включая остаток от деления, подробнее разобраны в уроке мини-курса об арифметических выражениях.

Команда if выполняет вложенные строки только тогда, когда проверка после неё верна. В примере она пропустит в print только числа, которые делятся на 6.

1for number in range(10, 21):2    if number % 6 == 0:3        print(number)  # 12, затем 18

Условия можно соединять словами and («и») и or («или»). При and должны выполниться обе проверки. При or достаточно хотя бы одной. Сначала проверяй каждую часть отдельно, а затем соединяй их.

Запись числа 5082 состоит из цифр 5, 0, 8 и 2. Это десятичная запись: каждая позиция показывает, сколько в числе тысяч, сотен, десятков и единиц. В задачах могут попросить сложить цифры, проверить, встречается ли среди них ноль, или найти последнюю цифру. Само число и цифры его записи — связанные, но разные вещи.

Для вычислений удобно по очереди отделять последнюю цифру: остаток от деления на 10 — это последняя цифра, а целочисленное деление // 10 убирает её. У отрицательного числа сначала берём модуль: знак минус не является цифрой. При нуле цикл не сделает ни одного шага, и сумма цифр останется равна нулю. abs даёт модуль числа. Цикл while повторяет команды, пока условие верно. Запись digit_sum += digit прибавляет новую цифру к накопленной сумме; remaining //= 10 делит оставшуюся часть числа на 10 нацело и сохраняет результат. В каждом повторе отдельно запоминаем последнюю цифру и прибавляем её к сумме.

1number = 50822remaining = abs(number)3digit_sum = 04 5while remaining > 0:6    digit = remaining % 107    digit_sum += digit8    remaining //= 109 10print(digit_sum)  # 15

В каждом повторе мы отделяем одну цифру и уменьшаем оставшуюся часть числа, поэтому цикл заканчивается. Как отделять цифры и что делать с нулём и отрицательным числом, подробно разобрано в уроке о цифрах числа. Устройство цикла отдельно объясняется в уроке о цикле while.

Для положительного числа можно перечислить числа, на которые оно делится нацело. Здесь натуральные числа — это 1, 2, 3 и все следующие положительные целые числа. Такие значения называют натуральными делителями исходного числа. У 18 это 1, 2, 3, 6, 9 и 18: каждое из них даёт остаток 0 при делении 18 на него.

Собственными делителями называют делители числа, кроме самого числа. Значит, у 18 собственные делители — 1, 2, 3, 6 и 9. Единицу включаем. Если условие просит сумму собственных делителей, складываем именно этот список и не добавляем 18.

Список в Python хранит несколько значений по порядку. Команда append добавляет значение в конец списка, а sum складывает все значения списка. Эти приёмы подробно разобраны в уроке Python о списках.

1number = 182proper_divisors = []3 4for candidate in range(1, number):5    if number % candidate == 0:6        proper_divisors.append(candidate)7 8print(proper_divisors)  # [1, 2, 3, 6, 9]9print(sum(proper_divisors))  # 21

Правая граница цикла равна самому числу, но не входит в перебор: это сделано специально, ведь мы ищем собственные делители.

У некоторых чисел список натуральных делителей особенно короткий. Например, у 7 есть только два таких делителя: 1 и 7. Число больше единицы, у которого ровно два натуральных делителя — единица и оно само, называется простым. Если делителей больше двух, число составное.

Единица не простая и не составная: у неё только один натуральный делитель. Ноль и отрицательные числа тоже не относятся к простым в этой теме. При проверке отдельного числа значения меньше 2 можно исключить заранее. В примере ниже мы всё же проверяем 1: подсчёт найдёт у неё один делитель, а условие «ровно два» не пропустит её в список простых. Оба способа дают правильный ответ.

1primes = []2for number in range(1, 11):3    divisor_count = 04    for candidate in range(1, number + 1):5        if number % candidate == 0:6            divisor_count += 17    if divisor_count == 2:8        primes.append(number)9 10print(primes)  # [2, 3, 5, 7]

Для каждого числа считаем его натуральные делители. Проверка divisor_count == 2 оставляет только простые. Это прямой и понятный способ для короткого диапазона; позже проверку можно ускорить, но сначала важно понять, что именно считает программа.

Делители удобно искать парами. Если 4 делит 36, то и 9 делит 36, потому что 4 × 9 = 36. Для каждого найденного меньшего делителя сразу известен второй: нужно разделить исходное число на первый. Например, у 36 пары такие: (1, 36), (2, 18), (3, 12), (4, 9) и (6, 6).

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

Два числа в каждой паре называют парными делителями. Квадратный корень из числа — это неотрицательное число, которое при умножении на себя даёт исходное. Например, квадратный корень из 36 равен 6, потому что 6 × 6 = 36. В любой паре делителей хотя бы один не больше квадратного корня: если бы оба были больше, их произведение тоже было бы больше исходного числа. Значит, достаточно проверить кандидатов до этой границы и для каждого найденного делителя сразу взять второй из пары.

Для 1 000 000 квадратный корень равен 1000: вместо 999 999 кандидатов проверим только числа от 1 до 1000. Если корень не целый, отдельного вычисления корня не нужно: проверяем кандидата, пока его квадрат не больше исходного числа. Так, для 50 проверка дойдёт до 7, потому что 7 × 7 = 49, а 8 × 8 = 64 уже больше 50. Если исходное число — квадрат, в середине получится пара из одинаковых значений. У 36 это (6, 6), и делитель 6 нужно посчитать один раз, а не два. Для чрезвычайно большого числа даже проверок до корня может оказаться много; тогда ищем, не помогает ли другое обязательное условие задачи сократить список проверяемых чисел.

Знак <= читается «меньше или равно». В цикле candidate += 1 означает «увеличить candidate на единицу». Знак != проверяет, что значения не равны. Поэтому условие paired != candidate отличает обычную пару от средней пары из одинаковых чисел.

1number = 362divisors = []3candidate = 14 5while candidate * candidate <= number:6    if number % candidate == 0:7        paired = number // candidate8        divisors.append(candidate)9        if paired != candidate:10            divisors.append(paired)11    candidate += 112 13print(divisors)  # [1, 36, 2, 18, 3, 12, 4, 9, 6]

Проверка candidate * candidate <= number останавливает цикл после середины пар и сравнивает только целые числа: для очень больших значений не нужно приближённо вычислять корень. Выражение number // candidate находит вторую часть пары: здесь деление всегда точное, потому что мы уже проверили делимость. В условии paired != candidate равная пара (например, 6 и 6) добавляется только один раз. Этот пример собирает все натуральные делители; если нужны только собственные, само число нужно исключить из результата.

Иногда нужны не все делители, а только те, которые отвечают ещё одному условию. Тогда проверяем каждое значение сразу после того, как нашли пару. Например, у 24 оставим собственные делители больше 5. Само число 24 исключаем, потому что собственным делителем оно не считается. Меньшее и большее значения проверяем отдельно: в паре (2, 12) подходит 12, хотя 2 не подходит.

1number = 242selected = []3candidate = 14 5while candidate * candidate <= number:6    if number % candidate == 0:7        paired = number // candidate8        if candidate > 5 and candidate < number:9            selected.append(candidate)10        if paired != candidate and 5 < paired < number:11            selected.append(paired)12    candidate += 113 14print(selected)  # [12, 8, 6]

Получились 12, 8 и 6 — это все собственные делители 24, которые больше 5. Порядок в списке повторяет порядок найденных пар; вручную те же числа можно записать по возрастанию: 6, 8, 12. Проверка paired != candidate также защищает середину квадрата от повтора. Если задача просит только количество подходящих делителей, можно вместо списка увеличивать счётчик на единицу за каждое подходящее значение; если нужен наибольший — сравнивать каждое подходящее значение с текущим наибольшим.

Тот же вывод помогает при проверке простоты. Для числа больше 1 достаточно попробовать делители от 2 до квадратной границы. Если хоть один делит число без остатка, число составное: его второй делитель уже известен. Если не нашлось ни одного, кроме 1 и самого числа делителей нет, значит, число простое. Например, 91 не простое: проверка дойдёт до 7 и обнаружит пару (7, 13). Для 97 кандидаты от 2 до 9 не дают нулевого остатка; дальше искать не нужно, поэтому 97 простое. Так можно ускорить проверку множества чисел, даже если полный список их делителей не требуется.

В условии иногда дана запись числа с неизвестными цифрами, например 2??. Каждый знак вопроса здесь обозначает одну десятичную цифру, а не любое количество символов. Поэтому у такой маски ровно сто вариантов: десять цифр для разряда десятков и десять для разряда единиц. Здесь первая цифра уже задана — это 2. Если бы вместо неё стоял вопросительный знак, ноль пришлось бы исключить: запись должна оставаться трёхзначным числом.

Запись с неизвестными местами назовём маской. Для перебора вставляем вместо каждого вопросительного знака цифры от 0 до 9, получаем целые числа и проверяем требование задачи. Для этого удобно вложить один цикл в другой: для каждой цифры десятков перебрать все цифры единиц. Каждый внутренний проход дописывает одну цифру, поэтому образуются все сочетания без пропусков. Цифры сначала записаны как текст. В записи "0123456789" цикл по очереди возьмёт каждый символ. Знак + соединяет эти части, а функция int превращает готовую запись в целое число.

В других условиях маска может содержать и звёздочку *. В ней звёздочка обозначает любое количество цифр, даже ни одной. Например, маске 3*5 подходят 35, 305 и 3005. Знак вопроса устроен иначе: маске 3?5 подходит 305, но не 35 и не 3005. Всегда прочитай определение знаков в самом условии. В практике ты решишь задачу с двумя знаками вопроса; звёздочку разберём здесь на небольшом примере.

1matches = []2for tens in "0123456789":3    for units in "0123456789":4        number = int("2" + tens + units)5        if number % 25 == 0:6            matches.append(number)7 8print(matches)  # [200, 225, 250, 275]

В этом примере проверяется делимость на 25. Среди чисел, которые заканчиваются на 00, 25, 50 или 75, проходят ровно четыре: 200, 225, 250 и 275. Внутренний цикл полностью завершает перебор единиц для каждой цифры десятков, затем внешний переходит к следующей цифре.

Сначала оцени число вариантов. У маски 2?? их всего 10 × 10 = 100, поэтому удобно сразу подставить цифры. У маски 2???? первая цифра тоже задана, а четыре вопросительных знака дают уже 10 × 10 × 10 × 10 = 10 000 вариантов. Если первый знак тоже вопросительный, ноль на этом месте исключаем: маска ???? задаёт 9 000 четырёхзначных чисел. Перебирать все числа до очень большой правой границы было бы расточительно, когда фиксированные цифры заранее исключают почти все числа. В таком случае строим только записи по маске, а затем проверяем делимость или нужный остаток. Если, наоборот, условие допускает только кратные заданному числу, можно заранее перебирать только их; выбор зависит от того, какой список кандидатов короче.

Ноль внутри записи допустим: из 7*2 можно получить 702. Но ведущий ноль не превращает запись в новое многозначное число: 025 — это запись числа 25, а не трёхзначное число. Для звёздочки особенно важна верхняя граница. Если по условию число не больше 800, маска 7*2 допускает пустую вставку (72) или одну цифру (от 702 до 792). Две вставленные цифры дали бы как минимум 7002 — уже больше 800. Значит, бесконечное на вид число вариантов на деле ограничено условием задачи.

Пустую запись в Python обозначают "". Сначала положим её в список возможных вставок, затем добавим по одной цифре от 0 до 9. Для каждой полученной записи составим число и проверим дополнительное условие — делимость на 9.

1middles = [""]2for digit in "0123456789":3    middles.append(digit)4 5matches = []6for middle in middles:7    number = int("7" + middle + "2")8    if number <= 800 and number % 9 == 0:9        matches.append(number)10 11print(matches)  # [72, 702, 792]

Проверим ответ независимо: 72 делится на 9, потому что 72 = 9 × 8. Среди трёхзначных записей 702 и 792 тоже делятся на 9; для остальных проверка остатка даст не ноль. Если граница станет больше и разрешит две цифры вместо звёздочки, нужно добавить в перебор все пары цифр, включая 00 и 09. При двух звёздочках общую допустимую длину распределяют между ними, но сначала снова выводят её из границы числа. Без верхней границы у звёздочки было бы бесконечно много возможных вставок, поэтому начинать такой перебор без ограничения нельзя.

Если к маске добавлено условие чётности, смотрим на последнюю цифру. Число чётное, когда оно делится на 2 без остатка: последняя цифра тогда равна 0, 2, 4, 6 или 8. Все десятки делятся на 2, поэтому остальные цифры на чётность не влияют. В записи 3?5? последняя позиция может быть только одной из этих пяти цифр, а другое условие всё равно проверяем отдельно.

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

Перед большим перебором проверь, можно ли сократить и внешний список чисел. Если по условию подходят только числа, делящиеся на 5, среди чисел от 100 до 200 достаточно проверять 100, 105, 110 и так далее до 200. Промежуточные числа заведомо не пройдут это обязательное условие. Но пропускать их можно только тогда, когда условие действительно исключает их из ответа; в примере ниже мы проверяем весь заданный отрезок.

Рассмотрим отрезок от 100 до 1000. Найдём первые пять чисел с ровно тремя натуральными делителями. Мы знаем, как считать делители парами: равная пара добавляет один делитель, обычная — два. Программа остановится после пятой находки. Затем вручную пересчитаем делители первых двух результатов, а остальные проверим по тому же образцу.

Функция len сообщает количество значений в списке, а break сразу завершает цикл. После перебора sum складывает найденные числа. Все эти команды уже встречались по отдельности; ниже они работают вместе.

1found = []2for number in range(100, 1001):3    divisor_count = 04    candidate = 15    while candidate * candidate <= number:6        if number % candidate == 0:7            paired = number // candidate8            divisor_count += 19            if paired != candidate:10                divisor_count += 111        candidate += 112 13    if divisor_count == 3:14        found.append(number)15        if len(found) == 5:16            break17 18print(found)  # [121, 169, 289, 361, 529]19print(sum(found))  # 1469

Правая граница 1001 включает число 1000. Для каждого числа цикл рассматривает делители до квадратной границы, поэтому один проход короче полного перебора всех значений от 1 до самого числа. Команда break завершает поиск после пятой находки. В выводе приведены сами пять чисел и их сумма — именно её напечатает последняя строка программы.

Проверь первые две находки без программы. У 121 пары (1, 121) и (11, 11), поэтому его натуральные делители — 1, 11 и 121. У 169 пары (1, 169) и (13, 13): делители 1, 13 и 169. У каждого числа получилось ровно три разных делителя. Аналогично проверь 289, 361 и 529: для них средние делители равны 17, 19 и 23.

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