8.02 Подсчет количества слов/чисел

Идея решения через itertools:

Мы хотим найти все пятизначные числа, которые содержат хотя бы один собственный делитель в записи числа. Для этого используем перебор всех возможных комбинаций цифр и проверку каждого числа на наличие подходящей цифры, совпадающей с собственным делителем.

1. Задаём алфавит цифр от "0"до "9". Это позволяет сгенерировать все пятизначные числа через функцию product.

2. Создаём функцию f(x), которая возвращает множество всех собственных делителей числа x, кроме 1 и самого числа. Для этого перебираем делители от 2 до квадратного корня числа включительно и добавляем как сам делитель, так и частное от деления.

3. Генерируем все 5-значные числа с помощью product(s, repeat=5):

     - Пропускаем числа, начинающиеся с "0 так как они не являются пятизначными.

     - Если в числе присутствует цифра "1 оно сразу подходит, потому что 1 делит любое число.

     - Иначе проверяем наличие в числе любой цифры, которая равна собственному делителю числа. Если такая цифра есть, число подходит и добавляется в множество для учёта уникальных чисел.

4. После перебора всех комбинаций выводим количество чисел в множестве, что даёт ответ задачи.

Решение через itertools:

from itertools import product # Импортируем функцию product для генерации комбинаций

# Функция для нахождения всех собственных делителей числа, кроме 1 и самого числа
def f(x):
    c = set() # Множество для хранения делителей
    for k in range(2, int(x ** 0.5) + 1): # Перебираем возможные делители до sqrt(x)
        if x % k == 0: # Если k делит число
            c.add(str(k)) # Добавляем делитель в множество как строку
            c.add(str(x // k)) # Добавляем частное от деления тоже как строку
    return c # Возвращаем множество делителей

s = "0123456789" # Цифры для генерации чисел
cnt = 0 # Счётчик подходящих чисел (не используется напрямую, используем множество)
t = set() # Множество для хранения уникальных чисел

# Генерация всех 5-значных чисел
for i in product(s, repeat=5):
    _i = "".join(i) # Преобразуем кортеж в строку числа
    if _i[0] == "0": # Пропускаем числа, начинающиеся с 0
        continue
    if "1" in _i: # Любое число с цифрой 1 подходит
        t.add(_i)
        continue
    for j in f(int(_i)): # Перебираем собственные делители числа
        if j in _i: # Если цифра делителя есть в числе
            t.add(_i) # Добавляем число в множество подходящих
            break
print(len(t)) # Выводим количество уникальных подходящих чисел