Обработка целочисленной информации

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

«Напишите программу, которая перебирает целые числа, большие 7 000 000, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи хотя бы одну цифру 1 и хотя бы одну цифру 6. В ответе для первых пяти найденных чисел запишите само число и наибольший из его простых множителей.»

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

Начнём с перебора и записи числа — этого уже хватит, чтобы проверить цифры множителей. Потом найдём делители и простые множители и решим задачу темы. Тема состоит из пяти подтем и дополнительного урока — у каждой своя страница:

1. Перебор и запись числа — ты сейчас здесь: проверки, перебор, цифры записи.
2. Делители парами — поиск делителей до √n, отбор и количество.
3. Числа с нужными делителями — ровно k делителей, больше всего делителей, величина M.
4. Простые числа и разложение — простые множители; решим задачу темы.
5. Маски — знаки ? и *, перебор с шагом и построение чисел по маске.
6. Вид числа по количеству делителей — дополнительный урок для огромных диапазонов.

Что значит «делится без остатка» и как проверить это в программе?

Число n делится на d, если остаток от деления равен нулю: n % d == 0. Разделим 17 на 5: пятёрка помещается в 17 три раза, и остаются две единицы — 17 = 5 · 3 + 2. В Python частное даёт 17 // 5, это 3, а остаток — 17 % 5, это 2.

Остаток всегда меньше делителя: будь он больше, из него сложилась бы ещё одна порция. У 20 и 5 порции заполняются ровно — 20 % 5 равно 0, значит, 20 делится на 5. А если число меньше делителя, порции нет совсем: 3 // 7 — это 0, а 3 % 7 — всё число, 3.

Обычное деление / здесь не нужно: 18 / 3 даёт дробное 6.0. Степень для больших границ пишут через **: 10⁹ — это 10 ** 9, а не 10 ^ 9.

Как перевести слова условия в проверку и не ошибиться на границе?

Слово за словом: «кратно» — остаток ноль, «больше» — строгое сравнение, «не превышает» — нестрогое, «и» — and, «или» — or. Похожие формулировки различаются одним знаком. Выбери формулировку:

кратно 7

n % 7 == 0остаток равен нулю

не кратно 7

n % 7 != 0остаток не ноль; != — «не равно»

нечётное

n % 2 != 0не делится на 2

больше 100

n > 100само 100 не подходит

не меньше 100

n >= 100100 подходит

не превышает 100

n <= 100100 подходит

на отрезке [100; 200]

100 <= n <= 200обе границы входят

or не значит «ровно одно из двух»: число 15 подходит под «делится на 3 или на 5», хотя делится на оба.

n = 15print(n % 3 == 0 and n % 5 == 0)print(n % 3 == 0 or n % 5 == 0)

Как проверить все числа отрезка подряд?

Циклом for по range. Правая граница range не входит, поэтому отрезок [L; R] — это range(L, R + 1). Выведем числа отрезка [10; 30], кратные 3:

for n in range(10, 31):    if n % 3 == 0:        print(n)

Граница 31 — чтобы проверить и само 30. А «числа, большие 7 000 000» начинаются с 7 000 001: сама граница в «больше» не входит.

Сколько чисел можно так перебрать? Десять миллионов простых проверок Python делает за секунду-другую, а миллиард — уже за несколько минут. Поэтому в масках будем перебирать умнее.

Как узнать о числе то, что видно в его записи: сколько в нём цифр, какая последняя, какова сумма цифр?

Превратить число в строку: str(n) — это его запись, у неё есть длина и отдельные символы. Последние цифры удобно брать остатком: n % 10, n % 100.

n = 50721s = str(n)print(len(s), s[0], s[-1])print(n % 10, n % 100, n // 100) digit_sum = 0for ch in s:    digit_sum += int(ch)print(digit_sum)

Пять цифр, первая 5, последняя 1. Остаток от деления на 10 — последняя цифра, на 100 — две последние, а n // 100 отбрасывает их. Сумму цифр считает цикл по символам записи: int(ch) превращает символ «7» в число 7.

Окончание с нулём проверяй по записи: у 7 и у 107 остаток n % 100 один — 7, но на «07» оканчивается только 107. Это проверка str(n).endswith('07').

Как проверить условие задачи темы: «множитель содержит в записи цифру 1 и цифру 6»?

Оператором in над записью: '1' in s истинно, если символ 1 есть в строке хотя бы раз. Группу цифр ищут так же, а s.count('53') считает, сколько раз она встречается. Проверку двух цифр оформим функцией: в строке с def — её имя и параметр p, а return возвращает ответ — True или False.

def has_1_and_6(p):    s = str(p)    return '1' in s and '6' in s print(has_1_and_6(61), has_1_and_6(163), has_1_and_6(71))

В 61 и 163 есть обе цифры, в 71 нет шестёрки. Такую проверку мы применим к каждому из двух множителей в задаче темы. Другие формулировки про цифры числа n — выбери; везде s = str(n):

содержит цифру 7

'7' in s

не содержит 0

'0' not in s

есть 2 или 3

'2' in s or '3' in s

«53» ровно один раз

s.count('53') == 1

оканчивается на 37

n % 100 == 37

В задаче темы нет верхней границы: «перебирает числа, большие 7 000 000, … первые пять найденных». Докуда же идти?

Пока не найдено пять: цикл while со счётчиком найденных. Число увеличиваем на каждом шаге, а счётчик — только когда число подошло. Найдём три первых числа больше 1000, которые делятся на 13 и содержат цифру 7:

n = 1001found = 0while found < 3:    if n % 13 == 0 and '7' in str(n):        print(n)        found += 1    n += 1

Числа идут по возрастанию и ни одно не пропущено, поэтому первые три успешные проверки — это три наименьших подходящих числа.

Если спрашивают о наибольших числах, идут вниз: range с шагом −1, а после нужного количества цикл прерывает break. Нижняя граница 0 не даст уйти в отрицательные числа, если подходящих меньше трёх:

found = []for n in range(999, 0, -1):    if n % 13 == 0 and '7' in str(n):        found.append(n)        if len(found) == 3:            break print(found)

• Делитсяn % d == 0
• Отрезок [L; R]range(L, R + 1)
• Первые k после Nс N + 1, while found < k
• Наибольшие kвниз по range и break
• Цифры записиstr(n), in, count
• Последние цифрыn % 10, n % 100