Задание 25 ЕГЭ по информатике

Что проверяет: Обработка целых чисел и делители

Задание 25 ЕГЭ по информатике проверяет тему «обработка целых чисел и делители». Ниже вы найдёте 2 варианта с условием, ответом и разбором, а под ними теория и алгоритм решения этого номера.

Решение

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

Текст распознан с изображения задания. Формулы, таблицы и рисунки смотрите на картинке ниже.

ЕГЭ по информатике: задание 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 входит в ЕГЭ по информатике. Это единственная страница сайта, где собраны все варианты этого номера: текст условия, картинка задания, правильный ответ, разбор решения и теория с алгоритмом. Остальные номера открываются в списке выше, а их перечень с темами есть в списке заданий ЕГЭ по информатике.