Решение
Задание 25 ЕГЭ по информатике
Что проверяет: Обработка целых чисел и делители
Задание 25 ЕГЭ по информатике проверяет тему «обработка целых чисел и делители». Ниже вы найдёте 2 варианта с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.
Решение
Теория к заданию 25 ЕГЭ по информатике: обработка целых чисел и делители
Нужно написать программу, которая перебирает числа и отбирает удовлетворяющие условию на делители.
Что нужно знать
- Делители ищут перебором от 2 до квадратного корня из числа: если i делит n, то делителями являются i и n / i.
- Минимальный делитель, не считая единицы, равен наименьшему найденному i; максимальный равен соответствующему ему n / i.
- Если делителей, кроме 1 и самого числа, нет, число простое, и значение по условию равно нулю.
- Перебор до корня даёт достаточную скорость для диапазонов порядка миллиона.
- Ответ оформляется таблицей: число и соответствующее ему значение.
Делители и перебор
- Делители ищутся перебором до квадратного корня из числа: если i делит N, то N/i тоже будет делителем.
- Такой перебор быстрее наивного в тысячи раз и укладывается в отведённое время.
- Не забывайте, что при i·i = N делитель засчитывается один раз.
- Количество делителей нечётно только у полных квадратов.
- Для условия «ровно два делителя» проверяйте простоту; для «ровно четыре» проверяйте, имеет ли число вид p·q или p³.
- Если нужен наибольший делитель, меньший самого числа, это N, делённое на наименьший простой делитель.
- Выводите пары «число и делитель» в том порядке и формате, который задан условием.
- Ограничьте диапазон перебора точно по условию: лишние итерации иногда дают лишние строки в ответе.
Как решать задание 25
- Напишите функцию поиска минимального и максимального собственного делителя.
- Перебирайте числа по возрастанию начиная с указанной границы.
- Для каждого числа вычислите требуемую величину.
- Проверьте условие и сохраняйте подходящие числа, пока не наберёте нужное количество.
- Заполните таблицу ответа в порядке возрастания чисел.
Разбор примера
Общая схема: найти в заданном диапазоне числа, имеющие ровно четыре различных делителя, и вывести число вместе с наибольшим делителем, меньшим самого числа.
- Пишем функцию подсчёта делителей перебором i от 1 до корня из N.
- Для каждого i, делящего N, добавляем в множество и i, и N // i.
- Идём циклом по числам заданного диапазона.
- Для каждого числа считаем размер множества делителей и сравниваем с четырьмя.
- Если условие выполнено, находим наибольший делитель, меньший N: это максимум множества без самого N.
- Выводим число и найденный делитель через пробел.
Ответпары «число и делитель»
Частые ошибки
- Перебирают делители до самого числа, и программа работает слишком долго.
- Забывают случай простого числа, когда собственных делителей нет.
Задание 25 входит в ЕГЭ по информатике. На этой странице собраны все варианты этого номера, которые разобраны на сайте: условие, правильный ответ и разбор решения. Остальные номера открываются в списке выше, а целиком все задания ЕГЭ по информатике с ответами собраны на странице предмета.