Задание 25. Информатика. ЕГЭ. Поляков-6426

(Р. Ягафаров) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

• символ «\(?\)» означает ровно одну произвольную цифру;
• символ «\(*\)» означает любую последовательность цифр произвольной длины; в том числе «\(*\)» может задавать и пустую последовательность.

Например, маске \(123{*}4{?}5\) соответствуют числа \(123405\) и \(12300425.\)

Среди натуральных чисел, не превышающих \(10^8,\) найдите все числа, соответствующие маске \(12{?}5{*}5{?}{?},\) которые представляют собой произведение двух различных простых чисел и делятся на \(311\) без остатка. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа – результат его деления на \(311.\)

def factor(n):
    divs = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            divs.append(i)
            n //= i
    if n > 1:
        divs.append(n)
    return divs

st = 1205500 + (311 - 1205500 % 311) % 311
for n in range(st, 12959599, 311):
    sn = str(n)
    if sn[:2] == '12' and sn[3] == '5' and sn[-3] == '5':
        divs = factor(n)
        if len(set(divs)) == len(divs) == 2:
            print(n, n // 311)