Шизофреник составляет пятизначные числа так, чтобы они содержали в своей записи хотя бы один собственный делитель. (Например число 12345 имеет делитель 5, а также имеет 5 в своём составе, значит оно подходит). Сколько таких чисел может составить шизофреник?
Примечание: собственным делителем называется любой его делитель, отличный от самого числа.
from itertools import product
def f(x):
c = set()
for k in range(2, int(x ** 0.5) + 1):
if x % k == 0:
c.add(str(k))
c.add(str(x // k))
return c
s = ’0123456789’
cnt = 0
t = set()
for i in product(s, repeat=5):
_i = ’’.join(i)
if _i[0] == ’0’:
continue
# Любые числа делятся на 1, поэтому если в числе есть цифра 1, оно сразу подходит
if ’1’ in _i:
t.add(_i)
continue
for j in f(int(_i)):
if j in _i:
t.add(_i)
break
print(len(t))
Ответ: 73655