Числа простые для экзамена ЕГЭ информатика: задачи и контекст
Числа простые для экзамена ЕГЭ информатика всегда вызывают вопросы у абитуриентов, потому что тема кажется узкой, но на практике встречается часто. Простые нужны в задачах на делители, криптографию, хеш-функции и работу со строками. Экзаменаторы любят их за четкий алгоритмический ответ, а проверяющие — за однозначную проверку результата.
Школьники обычно боятся запоминать много формул, однако здесь достаточно ясного определения: простым называют число, имеющее ровно два натуральных делителя — единицу и себя. Всё. Никаких дополнительных исключений, если не считать отрицательные и ноль, которые никогда не участвуют в заданиях. Такое лаконичное свойство рождает целую ветку алгоритмов, и ЕГЭ проверяет, умеет ли выпускник выбрать наиболее подходящий.
Важно понимать, где именно в кимах появляются простые. Чаще всего это: поиск всех простых до некоторой границы, нахождение k-го по счёту простого, проверка конкретного числа на простоту, либо работа с составными числами, где выяснить, сколько у них простых делителей. Секрет успешного решения — держать в голове базовые методы и уметь быстро переключаться между ними.
Простое определение и главные признаки
Стартуем с теории, но только той, что действительно нужна. Число два — единственное чётное простое. Начиная с трёх, проверять нужно лишь нечётные, потому что чётные автоматически имеют делитель два. Если число делится на любой простой, не превышающий его корень, оно составное. Это правило экономит время и уже встречается в объяснении официальных решений ФИПИ.
На реальном экзамене любят запутать задачей «почему достаточно корня». Логика проста: если у составного n нашёлся делитель d меньше корня, то второй делитель n/d будет больше корня. Значит, пара делителей обнаружена, и дальнейший поиск не нужен. Сам корень входит в проверку только если он целый. Умение быстро вывести этот аргумент спасает от лишнего кода и снижает вероятность ошибки.
Стоит помнить о малых исключениях. Единица не является ни простым, ни составным, а ноль и отрицательные значения в тестах не встречаются. Забыв о единице, легко потерять балл, потому что итоговый список делителей окажется длиннее, чем ждёт робот-проверяющий.
Алгоритм пробного деления
Пробное деление — главный учебный инструмент. Он работает медленнее современных решёт, зато показывает механику. Сначала исключаем чётные числа, потом делим на три, пять, семь и дальше по очереди на все нечётные до корня. В худшем случае сложность алгоритма равна O(√n). Для школьных ограничений до десяти миллиардов такого подхода хватает при грамотной оптимизации входа и выхода.
Практичный совет: не спешите писать деление в лоб. Сначала проверяем n <=3, затем n mod 2 и n mod 3. Далее можно идти шагом «шесть ± один», поскольку любое простое больше трёх лежит рядом с кратным шести. Таким приёмом число проверок снижается почти вдвое без сложной логики. Такую реализацию легко объяснить экспертам, потому что она базируется на школьной теории делимости.
Часть задач просит вывести список делителей или их количество. Тут пробное деление выполняет двойную работу: когда найден делитель d, можно сразу добавить в набор и n/d, если они различны. Итог собирается быстрее, чем при полном переборе, и соответствует формату ответов ЕГЭ.
Решето Эратосфена и его учебные модификации
Если нужно найти все простые до миллиона, ручное деление становится тормозом. Решето Эратосфена отключает составные путём отметки кратных. Создаём булев массив длиной m+1, где m — верхняя граница. Начинаем с двойки, идём до корня из m, обнуляем кратные. Время работы — O(m log log m), память — O(m). Этого достаточно для любого подзадания ЕГЭ.
Чтобы не тратить мегабайты, применяют компактные представления: маски по битам или отметку только нечётных индексов. Однако на экзамене избыточная оптимизация опасна. Ошибка в индексации сотрёт баллы. Лучше оставить классический массив, а после решить вопрос с памятью через условие задачи: организаторы никогда не дадут m выше десяти миллионов, что соответствует нескольким десяткам мегабайт.
В тестах, где нужно k-е простое, удобно сразу сохранять найденные в динамический список. Тогда лишний проход не потребуется. Плюс такого подхода — простота: одна функция строит решето и выдаёт результат, что ускоряет отладку.
Приёмы ускорения для больших n
Иногда авторы кидами предлагают гигантские числа, чтобы проверить умение мыслить. Тут помогают улучшения. Во-первых, комбинируют методы: для расчёта всех простых до корня используют решето, а дальше — пробное деление только на полученный список. Во-вторых, внедряют быстрый степенной тест Ферма или Миллера — Рабина. Последний даёт вероятностный ответ, но при ограниченном числе раундов шанс ошибки меньше одного на миллиард, что считается приемлемым.
Важно не переборщить. В реальных кимах встречаются числа до 2¹⁶, реже до 2³². На таких входах работает даже наивное деление. Поэтому избыточная сложность чаще вредит, чем помогает. Сначала пишите чистое решение, проверяйте его на крайних данных, и только затем вкручивайте профи-фичи, если время позволяет.
Код всегда проверяется таймерами, и пять секунд остаётся стандартом. Простой алгоритм на языке Python с оптимизациями ввода-вывода укладывается в полторы секунды. Помните об этом, прежде чем жертвовать читаемостью ради микросекунд.
Типовые задания и распространённые ловушки
Первая ловушка — граница диапазона. В условии указано «до n включительно», а студент проверяет «меньше n». Итоговое множество не совпадает с эталоном. Вторая — необходимость выводить делители упорядоченными. Часто встречается требование сортировки по возрастанию или убыванию, и пропуск даёт неверный ответ.
Популярное задание: «найдите наименьший делитель, отличный от единицы». Решается одним циклом до корня. Главное — сразу завершить, как только делитель найден, иначе код выйдет за лимит времени. Другая разновидность просит «количество простых в диапазоне». Тут выгодно заранее построить решето и дополнить его префиксными суммами, чтобы любой запрос отвечать за O(1).
Учителя также отмечают ошибку с типом переменной. Для больших n нужно использовать 64-битное целое. В Python проблемы нет, но в C++ выбирают unsigned long long. Неправильный тип обрезает число, и функция делимости ломается.
Код на Python под требования ЕГЭ
Ниже пример функции проверки простоты, которой достаточно для большинства задач.
- Обрабатываем n <=1 сразу, возвращая False.
- Числа 2 и 3 считаем простыми.
- Проверяем делимость на 2 и 3.
- Идём циклом i = 5; i*i <= n; i += 6:
- если n % i == 0 или n % (i + 2) == 0, возвращаем False.
- Возвращаем True.
Такой код занимает пять-шесть строк, легко набирается на языке, и при этом проходит все открытые тесты ФИПИ. Его плюсы — минимум магических чисел, прозрачная логика, отсутствие тяжёлых библиотек. Дополнительно можно обернуть алгоритм таймером, убедившись, что на worst-case входах функция укладывается в 0.1 секунды.
Когда нужна генерация списка, добавляется функция решета. Важно правильно настроить sys.stdin.readline для быстрого чтения и использовать .join при выводе. Эти детали дают бонусные миллисекунды, без которых большие наборы данных рискуют не пройти.
Практика и полезные ресурсы
Теория без решения задач быстро забывается. Поэтому заведите привычку каждый день решать хотя бы одну задачу на простые. Подойдёт любой тренажёр, однако я рекомендую официальный банк ФИПИ и несколько полных разборов на YouTube. Отрабатывайте разные формулировки, даже если алгоритм одинаковый. Разнообразие делает навык гибким.
Хорошая идея — вести файл с код-сниппетами. Туда помещайте рабочие функции решета, пробного деления и проверок. Перед экзаменом останется повторить четыре-пять готовых блоков, а не искать ошибки в старых проектах. Такой подход снижает стресс и экономит время.
Если нужна системная подготовка с обратной связью, посмотрите наш курс подготовки к ЕГЭ в онлайн школе el-ed.ru. Преподаватели дают короткие домашние задания, проверяют код и помогают привести решение к идеальному виду под формат проверки.
Последние штрихи перед экзаменом
За неделю до ЕГЭ сосредоточьтесь на повторении. Сначала перечитайте определения и признаки простоты, затем быстро наберите основные алгоритмы без подсказок. Ошибки фиксируйте сразу. После этого прорешайте минимум пять задач: две на проверку числа, две на поисковые диапазоны и одну комбинированную, где нужно вывести список делителей.
Накануне экзамена не экспериментируйте с новыми методами. Лучше отдохните, выспитесь и проверьте, что калькулятор, ручка и паспорт лежат на виду. Спокойная голова помнит алгоритмы лучше любого конспекта.
В день Х читайте условия медленно, выписывайте границы диапазона, не забывайте про единицу и проверяйте, что вывод соответствует формату. Тогда простые числа станут простыми баллами, а информатика принесёт заслуженные 100.