Задание 25 ЕГЭ по информатике. Обработка числовых данных

Содержание

Теория

Главные навыки

Создание и обработка списков: генераторы, циклы, фильтрация.
Сортировка списков (в том числе по пользовательскому ключу, например через лямбда-функции).
Базовая цель блока: научиться быстро и корректно получать список всех делителей числа и выделять числа по маске.

Два подхода к поиску делителей

1) Компактный (генератор списка)

def s(n):
    a = [i for i in range(2, n // 2 + 1) if n % i == 0]
    return a

Идея: перебираем целые от 2 до n//2 включительно; делителей больше n//2 не бывает; фильтр n % i == 0 оставляет только делители. Плюс — краткость; минус — скорость.

2) Быстрый (цикл до √n, «парами»)

def div(n):
    a = []
    for i in range(2, round(n**0.5) + 1):
        if n % i == 0:
            a.append(i)
            if i != n // i:
                a.append(n // i)
    return sorted(a)

print(div(36))

Ключевая идея: делители симметричны относительно √n. Перебираем только до √n, добавляя сразу пару делителей i и n//i; для точного квадрата центр добавляем один раз. Это резко ускоряет решение.

Прикладные модификации

Ровно два натуральных делителя (кроме 1 и самого числа)

def div(n):
    return [i for i in range(2, n // 2 + 1) if n % i == 0]

b = [i for i in range(2, 501) if len(div(i)) == 2]
print(b)
print(len(b))

Фильтруем по количеству найденных делителей.

Ровно два чётных делителя (включая само число)

def div(n):
    a = [i for i in range(2, n // 2 + 1) if n % i == 0 and i % 2 == 0]
    a.append(n)
    return a

b = [i for i in range(2, 501) if len(div(i)) == 2]
print(b)

Добавили фильтр i % 2 == 0 и явное включение числа n в список.

Получить сами списки делителей для всех подходящих чисел

def div(n):
    a = [i for i in range(2, n // 2 + 1) if n % i == 0 and i % 2 == 0]
    a.append(n)
    return a

b = [div(i) for i in range(2, 501) if len(div(i)) == 2]
print(b)

Теперь результат — «список списков», удобен для последующей сортировки/анализа.

Сортировка двумерного списка по пользовательскому ключу

def div(n):
    a = [i for i in range(1, n // 2 + 1) if n % i == 0]
    a.append(n)
    return a

def for_sort(a):
    return len(a)

arr = [div(i) for i in range(1, 20)]
arr.sort(key=for_sort, reverse=True)
for row in arr:
    print(row)

Сортируем по количеству делителей (убывание). Такой приём пригодится в задачах на сравнение «структур» чисел по их делителям.

Частые постановки

Множество разностей сомножителей

Для числа n перебираем пары i·(n//i) и собираем разности |(n//i) − i| под ограничениями.

def diffs(n):
    a = set()
    for i in range(2, round(n**0.5) + 1):
        if n % i == 0 and i != n // i:
            z = n // i - i
            if z <= 100:
                a.add(z)
        elif n % i == 0 and i == n // i:
            a.add(0)
    if n - 1 <= 100:
        a.add(n - 1)
    return a

ans = [x for x in range(1_000_000, 2_000_001) if len(diffs(x)) == 3]
print(ans)

Требуется три значения (≤100) в множестве разностей. Обратите внимание на обработку квадрата и крайнего случая n−1.

Генерация чисел по формулам и маскам

Числа вида `2^m · 3^n` в диапазоне

a = []
for n in range(1, 30, 2):       # n — нечётное
    for m in range(0, 30, 2):   # m — чётное
        val = 2**m * 3**n
        if 200_000_000 < val < 400_000_000:
            a.append(val)
print(sorted(a))

Перебор показателей с фильтрацией по диапазону.

Числа по маске (без регулярных выражений)

def in_mask(n):
    s = str(n)
    if s[0] == '1' and s[2:6] == '2139' and s[-1] == '4':
        return True
    return False

for i in range(2023, 10**10, 2023):
    if in_mask(i):
        print(i, i // 2023, sep='\t')

Маска «1?2139*4»: индексные проверки для фиксированных блоков, перебор по шагу делителя.

Примеры решений заданий

Задача 1. Все делители числа (быстро)

def divisors(n):
    res = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
    return sorted(res)

print(divisors(84))

Одна функция — две «половины» делителей, аккуратная обработка квадрата.

Задача 2. Натуральные ≤ 20 с их делителями, отсортированные по убыванию числа делителей

def div(n):
    a = [i for i in range(1, n // 2 + 1) if n % i == 0]
    a.append(n)
    return a

arr = [(i, div(i)) for i in range(1, 21)]
arr.sort(key=lambda t: len(t[1]), reverse=True)
for n, d in arr:
    print(n, d)

Пример расширяет идею пользовательского ключа сортировки на пары «число—делители».

Задача 3. Числа на отрезке, у которых множество разностей имеет ≥ 3 значений ≤ 100

def good(n):
    st = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            j = n // i
            st.add(abs(j - i) if abs(j - i) <= 100 else None) st.discard(None) return len(st) >= 3

ans = [x for x in range(1_000_000, 2_000_001) if good(x)]
print(ans[:10], '…', len(ans))

Вариант с безопасной фильтрацией «больше 100» и симметричным перебором.

Задача 4. Генерация чисел формы `2^m · 3^n` (m — чётное, n — нечётное) в заданном интервале

res = []
for n in range(1, 60, 2):
    for m in range(0, 60, 2):
        x = (2**m) * (3**n)
        if 200_000_000 < x < 400_000_000:
            res.append(x)
print(*sorted(set(res)), sep='\n')

Задача 5. Поиск по маске «1?2139*4», кратные 2023

def ok(n):
    s = str(n)
    return s.startswith('1') and s.endswith('4') and s[2:6] == '2139'

for x in range(2023, 10**10, 2023):
    if ok(x):
        print(x, x // 2023)

Лаконичная альтернатива на регулярных выражениях (по желанию)

import re
mask = re.compile(r'^1.\b2139.*4$')  # точное сопоставление шаблону
for x in range(2023, 10**7, 2023):   # в демо ограничим верх
    if mask.match(str(x)):
        print(x, x // 2023)

Короткий чек-лист к задачам блока

Для делителей всегда начинайте с перебора до √n и добавляйте пары; сортируйте в конце при необходимости.
Используйте множества, если нужно собирать «уникальные свойства» (например, разные разности).
Для «масок» без регулярок — проверяйте фиксированные позиции и подстроки; для ускорения перебирайте кратные делителю шага.
Сортировка по критерию: list.sort(key=...) или sorted(...) с лямбда-функцией.

Задания для тренировки

Вводные

Напишите функцию get_div(x). На вход функции подается целое число. Результат функции – последовательность всех возможных натуральных делителей (чисел, на которые можно разделить нацело исходное число х), за исключением числа 1 и самого числа х

Для создания последовательности, используйте генератор.

Например: get_div(18)=[2,3,6,9]

Используя функцию get_div из предыдущего задания, найдите все простые числа в диапазоне от 0 до 500. Напомню, что простыми числами, являются числа, которые делятся нацело только на 1 и на само себя.

Получившиеся числа поместите в список, используя генератор.

Используя функцию get_div из предыдущего задания, найдите все числа, имеющие ровно два натуральных делителя диапазоне от 0 до 500.

Получившиеся числа поместите в список, используя генератор.

Модифицируя функцию get_div из предыдущего задания, найдите все числа, имеющие ровно три четных натуральных делителя диапазоне от 0 до 500. Нечетные натуральные делители считать не нужно.

Получившиеся числа поместите в список, используя генератор.

Получите таблицу натуральных делителей из задания 4, поместите эти делители в двумерный массив, используя генератор.
Отсортируйте таблицу из задания 5 в порядке возрастания произведения всех натуральных делителей числа. Смотреть разбор
Используя функцию get_div найдите все числа, имеющие максимальное количество натуральных делителей. Добавьте в двумерный массив сами числа и все их натуральные делители.
Отсортируйте массив из задания 7 в порядке убывания чисел, у которых найдено максимальное число делителей. Смотреть разбор
Отсортируйте массив из задания 7 в порядке возрастания максимального делителя каждого числа. Смотреть разбор
Используя функцию get_div, найдите 5 чисел больших 500000, таких, что среди их делителей есть число, оканчивающееся на 8, при этом этот делитель не равен 8 и самому числу. В качестве ответа приведите 5 наименьших чисел, соответствующих условию
Напишите функцию M(N) — сумма двух наибольших различных натуральных делителей натурального числа N, не считая самого числа. Если у числа N меньше двух таких делителей, то M(N) считается равным 0.

Найдите 5 наименьших натуральных чисел, превышающих 10 000 000, для которых 0 < M(N) < 10 000.

На основе функции get_div, напишите новую функцию: diff_multi(x).
1. Функция получает на вход число.
2. Затем получает возможные пары сомножителей, произведение которых равно х
3. Получает разность этих сомножителей и добавляет ее в список
Используя функцию diff_multi(x), посчитайте количество чисел от 0 до 500, у которых множество разностей будет содержать не меньше трёх элементов, не превышающих 11
Найдите все натуральные числа N, принадлежащие отрезку [200 000 000; 400 000 000], которые можно представить в виде N = 2^m 3ⁿ, где m — чётное число, n — нечётное число. В ответе запишите все найденные числа в порядке возрастания
Сформируйте список из чисел [2023:2000000], кратных 2023
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

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

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

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

Напишите функцию in_mask(N), проверяющую соответствует ли число N маске 1?2139*4 Смотреть разбор

Главные навыки

Два подхода к поиску делителей

1) Компактный (генератор списка)

2) Быстрый (цикл до √n, «парами»)

Прикладные модификации

Ровно два натуральных делителя (кроме 1 и самого числа)

Ровно два чётных делителя (включая само число)

Получить сами списки делителей для всех подходящих чисел

Сортировка двумерного списка по пользовательскому ключу

Частые постановки

Множество разностей сомножителей

Генерация чисел по формулам и маскам

Числа вида 2^m · 3^n в диапазоне

Числа по маске (без регулярных выражений)

Примеры решений заданий

Задача 1. Все делители числа (быстро)

Задача 2. Натуральные ≤ 20 с их делителями, отсортированные по убыванию числа делителей

Задача 3. Числа на отрезке, у которых множество разностей имеет ≥ 3 значений ≤ 100

Задача 4. Генерация чисел формы 2^m · 3^n (m — чётное, n — нечётное) в заданном интервале

Задача 5. Поиск по маске «1?2139*4», кратные 2023

Короткий чек-лист к задачам блока

Задания для тренировки

Вводные

Простые

Средние

Сложные

Числа вида `2^m · 3^n` в диапазоне

Задача 4. Генерация чисел формы `2^m · 3^n` (m — чётное, n — нечётное) в заданном интервале