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

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

Определения

Делитель числа 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 - корень четвёртой степени; простых до него всего несколько десятков.