ЕГЭ Задание 25

Типы заданий № 25

В этой статье будет разобрано задание 25.

Рассмотрим типовые задачи из двадцать пятого задания ЕГЭ по информатике.

Данное задание относится к высокому уровню сложности.

Время выполнения задания ≈ 25 минут.

Данное задание проверяет умение создавать собственные программы (10–20 строк) для обработки целочисленной информации.

Задача 1

Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.

Напишите программу, которая перебирает целые числа, бо́льшие 700 000, в порядке возрастания и ищет среди них такие, для которых значение M оканчивается на 8. Выведите первые пять найденных чисел и соответствующие им значения M.

Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем – значение М. Строки выводятся в порядке возрастания найденных чисел.

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

Решение:

Решение Python

count = 0  # переменная счётчик
for i in range(700001, 800000):  # циклом перебираем числа большие 700 000
    M = 0  # значение M – сумма минимального и максимального натуральных делителей целого числа
    a = []  # список для добавления и сортировки чисел всех делителей числа i
    for j in range(2, int(i ** 0.5) + 1):  # цикл для поиска всех делителей числа i (j – числа с 2 до корня числа i включительно)
        if i % j == 0:  # если переменная j является делителем числа i
            a.append(j)  # то добавляем её в список a
            b = i // j  # ищем второй делитель
            if j != b:  # если он есть и не равен первому
                a.append(b)  # то и его добавляем в список a
    if a:  # если список не пустой
        a.sort()  # сортируем список по возрастанию
        M = a[0] + a[-1]  # Вычислим M (под индексом 0 после сортировки находится мин.делитель, под индексом -1 – максимальный)
        if M % 10 == 8:  # Если M оканчивается на 8
            print(i, M)  # Выводим такое число и M
            count += 1  # Добавляем +1 к счётчику, т.к. нашли такое M
            if count == 5:  # Когда уже вывели первые найденных пар чисел i M
                break  # прерываем основной цикл

Ответ:
700005 233338
700007 100008
700012 350008
700015 140008
700031 24168

Задача 2

Напишите программу, которая перебирает целые числа, большие 550 000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом.

Программа должна найти и вывести первые 6 таких чисел и соответствующие им значения упомянутых делителей.

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

Например, для числа 105 наибольший натуральный делитель 35 не является простым, для числа 15 наибольший натуральный делитель 5 — простое число, а для числа 13 такого делителя не существует.

Решение:

Решение Python

count = 0  # переменная счётчик
for i in range(550001, 1000000):  # циклом перебираем числа большие 550 000
    a = []  # список для добавления и сортировки чисел всех делителей числа i
    for j in range(2, int(i ** 0.5) + 1):  # цикл для поиска всех делителей числа i (j – числа с 2 до корня числа i включительно)
        if i % j == 0:  # если переменная j является делителем числа i
            a.append(j)  # то добавляем её в список a
            b = i // j  # ищем второй делитель
            if j != b:  # если он есть и не равен первому
                a.append(b)  # то и его добавляем в список a
    if a:  # если список не пустой
        a.sort()  # сортируем список по возрастанию
        flag = False  # переменная для сохранения результата проверки наибольшего натурального делителя
        for j in range(2, int(a[-1] ** 0.5) + 1):  # цикл для поиска всех делителей наибольшего натурального делителя числа i
            if a[-1] % j == 0:  # наибольший делитель – не простое число, раз найден ещё один делитель
                flag = True  # прошли проверку – значит flag в True
                break  # можно прервать цикл поиска 
        if flag:  # Если наибольший натуральный делитель числа i прошёл проверку 
            count += 1  # увеличиваем счётчик на 1
            print(i, a[-1])  # выводим число и его наибольший натуральный делитель
        if count == 6:  # просили вывести первые 6 чисел в ответ
            break  # прерываем основной цикл

Ответ:
550002 275001
550004 275002
550005 183335
550008 275004
550010 275005
550011 183337

Задача 3

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [258274; 258297], числа, имеющие ровно 4 различных делителя.

Выведите для каждого найденного числа два наибольших делителя в порядке возрастания.

Решение:

Решение Python

for i in range(258274, 258298):  # запускаем цикл перебора чисел в указанном диапазоне условия задачи
    a = []  # список в который добавим делители числа
    for j in range(1, int(i ** 0.5) + 1): # цикл для поиска всех делителей числа i
        if i % j == 0:  # если делитель найден
            a.append(j)  # добавим его в список 
            b = i // j  # ищем второй делитель
            if j != b:  # если он не равен первому
                a.append(b) # добавим и его тоже в список
    if len(a) == 4:  # если количество делителей у числа получилось равным 4
        a.sort()  # сортируем список делителей по возрастанию
        print(a[2], a[3])  # выводим предпоследний и последний делитель

Ответ:
15193 258281
1427 258287
1493 258289
36899 258293
51659 258295

Задача 4

Найдите все натуральные числа, принадлежащие отрезку [4234679; 10157812] и имеющие ровно три нетривиальных делителя.

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу.

Для каждого найденного числа запишите в ответе само число и его наибольший нетривиальный делитель.

Найденные числа расположите в порядке возрастания.

Решение:

Решение Python

for i in range(4234679, 10157813):  # запускаем цикл перебора чисел в указанном диапазоне условия задачи
    if round(i ** 0.5) ** 2 == i:  # проверяем целый корень из числа равен самому числу? Тогда могут быть три нетривиальных делителя
        a = []  # список в который добавим делители числа
        for j in range(2, int(i ** 0.5) + 1):  # циклом добавляем делители числа
            if i % j == 0:
                a.append(j)
                b = i // j
                if j != b:
                    a.append(b)
        if len(a) == 3:  # если делителя три
            a.sort()  # сортируем список, получая в конце списка наибольший делитель
            print(i, a[-1])  # выводим само число и его наибольший нетривиальный делитель

Ответ:
4879681 103823
7890481 148877

Задача 5

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

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

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

Среди натуральных чисел, не превышающих 10⁸, найдите все числа, соответствующие маске 1234*7, делящиеся на 141 без остатка.

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

Решение:

Для решения данной задачи(и подобных) элегантно в 4 строчки кода поможет функция fnmatch и такого же модуля Python. Подробнее можно прочитать в документации: https://docs.python.org/3/library/fnmatch.htmlЯ лишь приведу пример и поясню как эта функция работает на примере имени файла:

Пример использования fnmatch

from fnmatch import fnmatch

filename = 'example.txt'
pattern = '*.txt'
result = fnmatch(filename, pattern)
print(result)  # Вывод: True

Функция проверяет, соответствует ли строка filename строке шаблону pattern и возвращает True или False. Это мы и используем в решении задачи.

Решение Python

from fnmatch import fnmatch
# т.к. мы ищем числа которые делятся на 141 без остатка
for i in range(1234, 10**8+1, 141):  # перебираем все числа от 141 до 10⁸ с шагом 141
    if fnmatch(str(i), '1234*7'):  # функция проверит строку(число преобразовываем в строку) на соответствие маске 1234*7
        print(i, i // 141)  # Если прошли проверку выводим число и результат деления на 141

Ответ:
1234737 8757
12341307 87527
12342717 87537
12344127 87547
12345537 87557
12346947 87567
12348357 87577
12349767 87587

Задача 6 (Демоверсия ЕГЭ 2024)

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

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

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

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 1?2157*4, делящиеся на 2024 без остатка.

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

Решение:

Решение Python

Для решения данной задачи нам поможет функция fnmatch из стандартной библиотеки пакетов Python fnmatch. Функция fnmatch проверяет, соответствует ли строка с числом шаблонной строке и возвращает True если это так, иначе False.

from fnmatch import fnmatch
for i in range(2024, 10**10+1, 2024):
    if fnmatch(str(i), '1?2157*4'):
        print(i, i // 2024)

Начало цикла с 2024 т.к. вопрос стоит в проверки натуральных чисел которые делятся без остатка вплоть до числа 10. С шагом +2024 увеличиваем число. Далее внутри функции преобразуем число в строку, чтобы проверить её на соответствие паттерну(т.к. функция принимает строки). И выводим в цикле ответы тех чисел, которым функция вернула True(т.е. как раз те которые нам и нужны и они прошли проверку).

Ответ:
142157664 70236
1021575544 504731
1121571264 554136
1221577104 603546
1321572824 652951
1421578664 702361
1521574384 751766
1621570104 801171
1721575944 850581
1821571664 899986
1921577504 949396

Задача 7 (Демоверсия ЕГЭ 2025)

Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю. Напишите программу, которая перебирает целые числа, бо́льшие 800 000, в порядке возрастания и ищет среди них такие, для которых M оканчивается на 4. В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения M.

Например, для числа 20 М = 2 + 10 = 12.

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

Решение:

Решение Python

count = 0  # Счётчик до 5
for num in range(800001, 10000000):  # Запускаем цикл который перебирает целые числа от 800 000 по условию задания
    M = 0  # Изначально предполагаем что делителей у числа M нет
    dl_list = []  # Список где будем хранить все найденные делители числа
    # Перебираем вторым циклом все числа от исходного числа, которые могут оказаться делителями
    for del1 in range(2, int(num ** 0.5) + 1):
        if num % del1 == 0:  # Если делитель
            dl_list.append(del1)  # Добавить в список
            del2 = num // del1  # Второй делитель также проверяем
            if del1 != del2:
                dl_list.append(del2)  # Добавить в список второй делитель
    if len(dl_list) >= 1:  # Если делителей больше одного
        dl_list.sort()  # Сортируем по возрастанию
        M = dl_list[0] + dl_list[-1]  # M это сумма делителей = минимальный делитель + максимальный делитель
        if M % 10 == 4:  # Если M оканчивается на 4
            print(num, M)  # Выводим пару(число и M) как один из ответов на задачу
            count += 1
            if count == 5:  # Первые 5 чисел вывели, прерываем цикл, задача решена
                break

Ответ:
800004 400004
800009 114294
800013 266674
800024 400014
800033 61554

Задача 8 (Демоверсия ЕГЭ 2025 Вариант ИЛИ)

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

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

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

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

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

Решение:

Решение Python

from fnmatch import fnmatch
for i in range(1917, 10**10+1, 1917):
    if fnmatch(str(i), '3?12?14*5'):
        print(i, i // 1917)

Начало цикла с 1917 т.к. вопрос стоит в проверки натуральных чисел которые делятся без остатка вплоть до числа 10¹⁰. С шагом +1917 увеличиваем число. Далее внутри функции преобразуем число в строку, чтобы проверить её на соответствие паттерну(т.к. функция принимает строки). И выводим в цикле ответы тех чисел, которым функция вернула True(т.е. как раз те которые нам и нужны и они прошли проверку).

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

Задача 9 (Демоверсия 2026 и вариант ИЛИ)

Условие и решение такое же как в демоверсии 2025 года. Здесь это задачи Задача 7, 8 выше.

Попробуйте сами запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.