Что проверяет задание

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

Определения

Делитель числа n, натуральное d, для которого n делится на d нацело. Делители ходят парами: если d делит n, то n / d тоже делит n.

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

Составное число, натуральное больше 1, не являющееся простым.

Наименьший простой делитель, наименьшее простое p, делящее n. Для чётных это 2.

Факторизация, представление n произведением простых степеней p₁^k₁ · p₂^k₂ · …

Количество делителей по факторизации: если n = p₁^k₁ · … · pₘ^kₘ, то число делителей равно (k₁ + 1) · … · (kₘ + 1).

Сумма делителей, сумма всех d, делящих n, иногда без самого n (тогда это сумма собственных делителей).

Маска числа, шаблон десятичной записи. Символ цифры означает фиксированную цифру, звёздочка, любую последовательность цифр (возможно пустую, если не сказано иное), вопрос, ровно одну произвольную цифру. Точные правила смотрят в условии.

Диапазон, отрезок натуральных чисел [A, B], внутри которого ищут.

Масштаб перебора

Перебор всех n от A до B с проверкой делителей до √n годится, пока диапазон не слишком широк. Если диапазон огромен, а маска жёсткая, выгоднее порождать числа по маске, а не проверять каждое подряд.

Для «найдите все простые в диапазоне» достаточно решета на отрезке: вычёркивать кратные простым до √B.

Общий алгоритм решения

1. Выписать диапазон и критерий: простота, набор делителей, сумма делителей, соответствие маске.
2. Выбрать генерацию: идти по n или порождать кандидатов по маске.
3. Для каждого кандидата найти нужную арифметическую характеристику, не включая лишние делители (1 и n, по условию).
4. Отфильтровать по неравенствам: «ровно k делителей», «максимальный делитель, не равный n», «делитель оканчивается на …».
5. Собрать ответ в требуемом порядке: обычно по возрастанию n.
6. Если просят два числа в строке, например, само n и его делитель, соблюдать формат пары.

Программа построчно

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

Разберём программу на условии:

Рассматриваются целые числа, большие 150000. Найдите первые пять чисел, у которых количество различных натуральных делителей больше 12.

def divisors(n):
    dels = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            dels.append(i)
            if i != n // i:
                dels.append(n // i)
    return sorted(dels)

count = 0
n = 150000
while count < 5:
    n += 1
    if len(divisors(n)) > 12:
        print(n)
        count += 1

def divisors(n): … return sorted(dels) - функция возвращает список всех делителей числа по возрастанию. Подробно - в разделе «Функция divisors».

count = 0 / n = 150000 - сколько чисел уже найдено и с какого числа начинаем (само 150000 не подходит: нужны числа больше него).

while count < 5: / n += 1 - берём следующее число, пока не найдено пять. Подробно - в разделе «Первые пять чисел».

if len(divisors(n)) > 12: - len - длина списка, то есть количество делителей.

print(n) / count += 1 - печатаем найденное число и увеличиваем счётчик.

Функция divisors

def divisors(n):
    dels = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            dels.append(i)
            if i != n // i:
                dels.append(n // i)
    return sorted(dels)

Делители идут парами: если i делит n, то и n // i делит n. Например, для 36: 1 и 36, 2 и 18, 3 и 12, 4 и 9, 6 и 6. Меньший делитель пары не больше корня из n, поэтому достаточно перебрать i от 1 до √n - это в тысячи раз быстрее, чем перебирать все числа до n.

• int(n ** 0.5) - целая часть корня; + 1 - чтобы сам корень тоже попал в range;
• n % i == 0 - i делит n без остатка: добавляем i и его пару n // i;
• if i != n // i - у точного квадрата корень стоит в паре сам с собой (6 и 6 для 36): добавляем его один раз;
• sorted(dels) - список по возрастанию: dels[0] - наименьший делитель (1), dels[-1] - само n, dels[-2] - наибольший делитель, не равный n.

Что получают из списка:

• количество делителей - len(divisors(n));
• сумма всех делителей - sum(divisors(n));
• делители без 1 и самого числа («нетривиальные») - [x for x in divisors(n) if x != 1 and x != n];
• наименьший и наибольший нетривиальный - первый и последний элементы этого списка.

Внимание: в шаблоне count_dels_2 цикл написан как range(2, root) - он не доходит до самого корня. Если n не точный квадрат, но делится на root (например, n = 12, root = 3), делители 3 и 4 теряются. Правильная граница - int(n ** 0.5) + 1.

Первые пять чисел

count = 0
n = 150000
while count < 5:
    n += 1
    if условие:
        print(n)
        count += 1

• while count < 5: - цикл «пока»: повторяется, пока найдено меньше пяти чисел. Сколько чисел придётся проверить, заранее неизвестно, поэтому for здесь неудобен;
• n += 1 стоит в начале цикла: первое проверяемое число - 150001;
• если нужно печатать ещё и значение (например, сумму делителей), пишут print(n, r) - два числа через пробел, как в строке таблицы ответа;
• последняя цифра числа - остаток от деления на 10: «R оканчивается на 4» → r % 10 == 4.

Маска: перебор кратных

«Среди натуральных чисел, не превышающих 10⁹, найдите числа по маске 2?4478*9, делящиеся на 1991».

from fnmatch import fnmatch

for i in range(1991, 10 ** 9 + 1, 1991):
    if fnmatch(str(i), "2?4478*9"):
        print(i, i // 1991)

• перебирать все числа до 10⁹ слишком долго. Нужны только кратные 1991 - поэтому range с шагом 1991: 1991, 3982, 5973, … Их в 1991 раз меньше;
• i // 1991 - частное, которое просят записать во втором столбце;
• если спрашивают количество - заводят счётчик; наименьшее и наибольшее - собирают числа в список и печатают min и max.

fnmatch

fnmatch(строка, маска) из модуля fnmatch проверяет, подходит ли строка под маску:

• ? - ровно один любой символ;
• * - любая последовательность символов, в том числе пустая;
• остальные символы должны совпасть точно.

Число сравнивают в виде строки: fnmatch(str(i), "123*4?5"). Например, fnmatch("12300405", "123*4?5") - True: «123», потом «00» вместо *, «4», «0» вместо ?, «5».

Ровно три делителя: квадрат простого

Число имеет ровно три делителя только если это квадрат простого числа p: делители 1, p и p². У любого другого числа делителей либо два (простое), либо четыре и больше.

def is_simple(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

for n in range(120355, 139712 + 1):
    r = int(n ** 0.5)
    if r * r == n and is_simple(r):
        print(n)

• is_simple - проверка на простоту: если нашёлся делитель от 2 до √n, число составное;
• r * r == n - n точный квадрат, is_simple(r) - его корень простой;
• такая проверка мгновенная, а подсчёт всех делителей для каждого числа отрезка был бы в сотни раз дольше.

«Ровно один нетривиальный делитель» - то же самое: из 1, p, p² нетривиальный только p.

Аналогично ровно пять делителей (1, p, p², p³, p⁴) - у четвёртой степени простого числа. Тогда перебирают не числа, а сами простые p:

for p in range(2, int(25425903 ** 0.25) + 2):
    if is_simple(p) and 4875564 <= p ** 4 <= 25425903:
        print(p ** 4)

** 0.25 - корень четвёртой степени; простых до него всего несколько десятков.

Маска с особыми символами

Иногда в маске есть символы, которых нет в fnmatch: «Ч» - одна чётная цифра, «Н» - одна нечётная, «#» - последовательность чётных цифр и т. п. Тогда маску переводят в регулярное выражение и проверяют модулем re.

«Среди чисел, не превышающих 10⁹, найдите числа по маске 1Ч2*5Н, делящиеся на 2023».

import re

mask = re.compile(r"1[02468]2\d*5[13579]")

for x in range(2023, 10 ** 9 + 1, 2023):
    if mask.fullmatch(str(x)):
        print(x, x // 2023)

Как переводить символы маски:

• цифра остаётся цифрой: 1 → 1;
• одна любая цифра (?) → \d;
• любая последовательность цифр, в том числе пустая (*) → \d*;
• одна чётная цифра → [02468], одна нечётная → [13579];
• последовательность чётных цифр произвольной длины → [02468]*;
• ровно три любые цифры → \d{3}, ровно три нечётные → [13579]{3}.

Квадратные скобки - «один символ из перечисленных», * после элемента - «сколько угодно раз, в том числе ни разу», {3} - «ровно три раза».

• re.compile(r"...") готовит выражение один раз, до цикла; буква r перед строкой нужна, чтобы \d не считалось спецсимволом строки;
• mask.fullmatch(str(x)) - запись числа целиком подходит под выражение (а не только её часть);
• перебор, как и с fnmatch, идёт только по кратным - с шагом делителя.

Простые делители числа

Простые делители находят разложением на множители: делим число на d = 2, 3, 4, … пока делится. Каждый раз, когда d делит число, d простое: все меньшие простые множители уже «выдавлены» из числа.

def prime_divisors(n):
    primes = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            primes.append(d)
            while n % d == 0:
                n //= d
        d += 1
    if n > 1:
        primes.append(n)
    return primes

• while d * d <= n: - делители ищем до корня из оставшегося n; после деления n уменьшается, и цикл заканчивается быстрее;
• while n % d == 0: n //= d - убираем множитель d целиком (для 72 = 2·2·2·3·3 двойка добавится один раз);
• if n > 1: - то, что осталось после цикла, - последний простой делитель (он больше корня, поэтому цикл до него не дошёл);
• список получается по возрастанию: primes[0] - наименьший простой делитель, primes[-1] - наибольший.

«Не считая самого числа»: у простого n единственный простой делитель - само n. Его убирают, и список становится пустым:

p = [x for x in prime_divisors(n) if x != n]
m = p[0] + p[-1] if p else 0

Запись a if условие else b - «a, если условие верно, иначе b»: если простых делителей нет, значение по условию равно нулю.

Произведение двух простых

«Число - произведение ровно двух простых множителей, не обязательно различных». Ищем наименьший делитель d числа n: он всегда простой. Число подходит, только если второй множитель n // d тоже простой.

def is_simple(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def two_primes(n):
    for d in range(2, int(n ** 0.5) + 1):
        if n % d == 0:
            q = n // d
            if is_simple(q):
                return d, q
            return None
    return None

• первый делитель, найденный в цикле, - наименьший, поэтому он простой;
• return None сразу после первого делителя: если n // d составное, множителей больше двух, искать дальше незачем;
• если цикл не нашёл делителей до корня, n простое - это не произведение двух простых;
• d ≤ q: d - меньший множитель, q - больший («не обязательно различных» - значит, подходит и квадрат простого, d = q).

Дополнительные условия на множители проверяют до is_simple(q), чтобы не тратить время на проверку простоты зря. Например, «каждый содержит ровно одну цифру 7»: str(d).count("7") == 1 and str(q).count("7") == 1.

Условия на найденное значение

Когда значение (сумма делителей, сумма наименьшего и наибольшего простого делителя и т. п.) посчитано, его проверяют по условию задачи:

• «оканчивается на 4» - m % 10 == 4; «оканчивается на 63» - две последние цифры: m % 100 == 63;
• «при делении на 7 даёт в остатке 3» - m % 7 == 3;
• «кратно 17» - m % 17 == 0; обратите внимание, что 0 тоже кратен 17, поэтому в условиях часто пишут «не равно нулю и кратно»;
• «является палиндромом» - запись числа совпадает с перевёрнутой: str(m) == str(m)[::-1];
• «является полным квадратом натурального числа» - m > 0 and int(m ** 0.5) ** 2 == m;
• «является простым числом» - is_simple(m);
• «содержит последовательность цифр 567 ровно один раз» - str(m).count("567") == 1.

Несколько условий соединяют через and: число печатаем, только если выполнены все.

Отрезок: подсчёт чисел

«Рассматривается множество целых чисел отрезка [12014; 49635], остаток от деления которых на 13 равен 7, и при этом они не делятся ни на 5, ни на 12. Найдите количество таких чисел и минимальное из них».

found = []
for x in range(12014, 49635 + 1):
    if x % 13 == 7 and x % 5 != 0 and x % 12 != 0:
        found.append(x)
print(len(found), min(found))

• range(12014, 49635 + 1) - правая граница отрезка входит, поэтому + 1;
• «делится на 5» - x % 5 == 0, «не делится» - x % 5 != 0; «делится на 7 или 11» - (x % 7 == 0 or x % 11 == 0), скобки обязательны рядом с and;
• подходящие числа собираем в список: len - их количество, min и max - наименьшее и наибольшее.

Маска без звёздочки: порождаем числа

Если граница огромная (10¹³), а делитель маленький, кратных слишком много: перебор с шагом делителя займёт минуты. Зато маска без «*» задаёт числа одной длины, и их немного: каждый «?» - одна из 10 цифр. Маска 12?345?67089? - это всего 10³ = 1000 чисел.

from itertools import product

mask = "12?345?67089?"
for digits in product("0123456789", repeat=3):
    s = mask
    for d in digits:
        s = s.replace("?", d, 1)
    x = int(s)
    if x % 206 == 0 and x <= 10 ** 13:
        print(x, x // 206)

• product("0123456789", repeat=3) перебирает все тройки цифр: (0, 0, 0), (0, 0, 1), …, (9, 9, 9);
• s.replace("?", d, 1) - третий аргумент 1: заменяется только первый оставшийся «?», так цифры встают по порядку;
• тройки идут по возрастанию, числа одной длины - тоже, поэтому печатаются по возрастанию;
• если маска начинается с «?», первая цифра не может быть нулём - такие наборы пропускают.