Задание 25 ЕГЭ информатика

Программа обработки целых чисел

Как это было в демоверсии 2027

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

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

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

Источник: ФИПИ, проект демоверсии ЕГЭ 2027, с. 21

Решение и ответ

Для каждого числа ищем наименьший делитель $d$ (он простой). Число — произведение ровно двух простых, если $d^2 \le n$ и $n / d$ тоже простое.
Остаётся проверить, что в записи каждого множителя «16» встречается ровно один раз: str(d).count('16') == 1.

def prime(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return n > 1

n, k = 1103285717, 0
while k < 5:
    n += 1
    d = 2
    while d * d <= n and n % d:
        d += 1
    q = n // d
    if d * d <= n and prime(q) and str(d).count('16') == 1 and str(q).count('16') == 1:
        print(n, d)
        k += 1

Ответ (по строкам: число и наименьший множитель): 1103299319 1693; 1103309477 1693; 1103322107 16187; 1103323021 1693; 1103328547 3169.

Ответ: 1103299319 1693 1103309477 1693 1103322107 16187 1103323021 1693 1103328547 3169

Все примеры задания 25 из демоверсии (2) →