Е25.57 каждый из которых содержит в своей записи ровно одну комбинацию цифр 16

Напишите программу, которая перебирает целые числа, большие 1 104 285 717, в порядке возрастания и ищет среди них числа, представляющие собой произведение двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно одну комбинацию цифр 16.

В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце — для каждого из них соответствующий наименьший из найденных множителей.

Количество строк в таблице для ответа избыточно.

Резервная волна ЕГЭ по информатике 22.06.2026 – задание №25

Решение:

Решение на Python

def is_prime(x):
    if x < 2:
        return False

    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False

    return True


def good(x):
    return is_prime(x) and str(x).count('16') == 1


N = 1_104_285_717
ans = []

for a in range(2, 40000):
    if good(a):
        b = N // a + 1

        k = 0
        while k < 5:
            if good(b):
                ans.append((a * b, a))
                k += 1
            b += 1


ans.sort()

for x, a in ans[:5]:
    print(x, a)

def is_prime(x):

if x < 2:

return False

for i in range(2, int(x ** 0.5) + 1):

if x % i == 0:

return False

return True

def good(x):

return is_prime(x) and str(x).count('16') == 1

N = 1_104_285_717

ans = []

for a in range(2, 40000):

if good(a):

b = N // a + 1

k = 0

while k < 5:

if good(b):

ans.append((a * b, a))

k += 1

b += 1

ans.sort()

for x, a in ans[:5]:

print(x, a)

Объяснение решения

По условию нужно найти числа, большие 1 104 285 717, которые являются произведением двух простых множителей.

При этом каждый из двух множителей должен содержать в своей записи ровно одну комбинацию цифр 16.

Сначала создадим функцию для проверки числа на простоту:

def is_prime(x):
    if x < 2:
        return False

    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False

    return True

def is_prime(x):

if x < 2:

return False

for i in range(2, int(x ** 0.5) + 1):

if x % i == 0:

return False

return True

Если число имеет делитель от 2 до квадратного корня из числа, оно не является простым.

Если ни одного делителя не найдено, функция возвращает True.

Затем создаём функцию good(x):

def good(x):
    return is_prime(x) and str(x).count('16') == 1

def good(x):

return is_prime(x) and str(x).count('16') == 1

Она одновременно проверяет два условия:

число x является простым;
в его десятичной записи комбинация 16 встречается ровно один раз.

Запоминаем границу из условия:

N = 1_104_285_717

1 2	N = 1_104_285_717

В список ans будем добавлять найденные числа и их меньшие множители:

ans = []

ans = []

Теперь перебираем возможный первый множитель a:

for a in range(2, 40000):
    if good(a):

for a in range(2, 40000):

if good(a):

Нам интересны только такие значения a, которые являются простыми и содержат ровно одну комбинацию 16.

Для каждого подходящего a нужно найти второй множитель b.

Так как произведение должно быть больше N, должно выполняться:

a * b > N

a * b > N

Следовательно, минимальное возможное значение второго множителя можно сразу найти так:

b = N // a + 1

1 2	b = N // a + 1

Это позволяет не перебирать значения b с самого начала.

Далее ищем первые 5 подходящих значений b:

k = 0

while k < 5:
    if good(b):
        ans.append((a * b, a))
        k += 1
    b += 1

k = 0

while k < 5:

if good(b):

ans.append((a * b, a))

k += 1

b += 1

Если b тоже является простым числом и содержит ровно одну комбинацию 16, то число

a * b

a * b

удовлетворяет условию задачи.

В список добавляем пару:

(a * b, a)

1 2	(a * b, a)

Первое значение — найденное число, второе — меньший множитель.

Для каждого подходящего a ищем несколько значений b, потому что один и тот же меньший множитель может входить сразу в несколько первых подходящих чисел.

Например, множитель 1669 встречается сразу в нескольких ответах.

После завершения поиска сортируем все найденные числа по возрастанию:

ans.sort()

1 2	ans.sort()

И выводим первые 5:

for x, a in ans[:5]:
    print(x, a)</code><code>

for x, a in ans[:5]:

print(x, a)</code><code>

Ответ:

1104293251 16691
1104315547 1669
1104332237 1669
1104342251 1669
1104352547 163