Задание 25 демоверсии ЕГЭ 2027 по информатике: разбор

Программа обработки целых чисел. Реши сам, потом открой решение.

Пример 1

Напишите программу, которая перебирает целые числа, бо́льшие 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

Пример 2

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

– символ «?» означает ровно одну произвольную цифру;

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

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих $10^{10}$ , найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка.

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

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

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

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

Без «*» в маске 8 цифр, а числа не длиннее 10 цифр ( $10^{10}$ маске не подходит). Значит, ищем 8-, 9- и 10-значные числа, начинающиеся с 3.
Перебираем только кратные 1917 в этих диапазонах и сверяем строку с маской — fnmatch понимает «?» и «*» именно так, как в условии.

from fnmatch import fnmatch

for lo in (3 * 10**7, 3 * 10**8, 3 * 10**9):   # числа из 8, 9 и 10 цифр, начинаются с 3
    for x in range((lo + 1916) // 1917 * 1917, lo // 3 * 4, 1917):
        if fnmatch(str(x), '3?12?14*5'):
            print(x, x // 1917)

Ответ (по строкам: число и частное): 351261495 183235; 3212614035 1675855; 3412614645 1780185; 3712414275 1936575; 3912414885 2040905.

Ответ: 351261495 183235 3212614035 1675855 3412614645 1780185 3712414275 1936575 3912414885 2040905