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

Задание 25 ЕГЭ по информатике проверяет умение писать программу для обработки натуральных чисел: перебор чисел в заданном диапазоне, разложение на простые множители, работу с цифрами числа, использование решета Эратосфена, быстрое возведение в степень, а также анализ чисел по маске с символами ? и…

Что нужно знать

• Задание 25 относится к части 1, ответ записывается в виде таблицы (последовательность цифр), проверяется автоматически.
• Максимальный первичный балл за задание — 1; общий первичный балл за всю работу — 29.
• Время выполнения всего экзамена — 3 часа 55 минут (235 минут), на задание 25 рекомендуется тратить не более 20–30 минут.
• Необходимо уметь перебирать числа в заданном диапазоне (иногда до 10^10) с помощью цикла, но с оптимизацией (например, перебор только подходящих чисел по маске или использование решета).
• Разложение числа на простые множители: проверка делимости на 2, затем перебор нечётных делителей до sqrt(n), подсчёт количества простых множителей (с учётом кратности).
• Проверка, является ли число простым: перебор делителей до sqrt(n) или решето Эратосфена для диапазона.

Термины и понятия

• Простое число: натуральное число, имеющее ровно два различных натуральных делителя — единицу и само себя.
• Разложение на простые множители: представление числа в виде произведения простых чисел.
• Решето Эратосфена: алгоритм поиска всех простых чисел до заданного предела путём последовательного вычёркивания кратных.
• Маска: шаблон для числа, содержащий цифры и символы «?» (одна любая цифра) и «*» (любая последовательность цифр).
• Позиционная система счисления: система, в которой значение каждой цифры зависит от её позиции.
• Быстрое возведение в степень: алгоритм вычисления a^b за O(log b) умножений.
• Перебор: последовательный просмотр всех возможных вариантов.
• Делимость: свойство числа делиться на другое без остатка.

Частые ошибки

• Неверное понимание условия «ровно один раз содержит 16»: ученик считает вхождения подстроки «16» без учёта перекрытий или наоборот, или путает с «содержит 16» (без «ровно один раз»).
• Ошибки при работе с маской: неправильная замена «?» и «*», забывают про возможность пустой последовательности для «*», не учитывают, что «?» — ровно одна цифра.
• Не учитывают, что множители могут быть одинаковыми (например, 49 = 7*7, где 7 — простое, но если 7 содержит «16»? — нет, но в общем случае).
• При разложении на простые множители останавливаются, не проверив, что оставшееся число больше 1 и является простым.

Как пройти тему

В курсе «Информатика» тема «Задание 25. Обработка натуральных чисел» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Задание 11. Кодирование изображений и звука
• Задание 16. Анализ алгоритмов
• Задание 18. Системы счисления
• Задание 24. Обработка символьных данных
• Задание 26. Массивы и последовательности

← Предыдущая тема: Задание 24. Обработка символьных данных
Следующая тема: Задание 26. Массивы и последовательности

Все темы: ЕГЭ по информатике