Квадратный корень в задачах ЕГЭ по информатике: как оптимизировать перебор делителей

Квадратные корни — зачем они вообще нужны

** изображение создано или обработано с помощью ИИ.

Название «квадратные корни для ЕГЭ по информатике» звучит математически, но пугаться не стоит. Корни здесь — не сложные формулы на всю доску, а обычный инструмент, который помогает писать более быстрый код.

Я готовлю учеников к информатике и сам когда-то думал: «Зачем здесь корень?» Потом понял простую вещь: корень часто сокращает время работы программы. А на ЕГЭ скорость выполнения — важный фактор.

Пример: проверка числа на простоту. Можно делить число на все числа от 2 до n-1. При больших n программа начнёт работать очень долго. Достаточно проверить делители до квадратного корня из n. Почему? Если делитель больше корня, то парный ему делитель уже меньше корня.

— То есть корень нужен не ради математики?

— Именно. Он нужен ради эффективности алгоритма.

Я объясняю это через пару нюансов. У числа 36 есть пара 4 и 9. Один множитель меньше, равен корню (6), другой — больше, равен. Если до 6 не нашли ни одного делителя, дальше искать смысла нет.

Такой приём встречается в задачах на делители, простые числа, оптимизацию перебора. А ещё он полезен, когда нужно аккуратно работать с границами цикла. Ошибка на один шаг может сломать ответ. Обидно, когда логика верная, а программа пропускает число 49. Семёрка потом смотрит укоризненно.

Где квадратные корни появляются в заданиях ЕГЭ

** изображение создано или обработано с помощью ИИ.

Квадратные корни в информатике редко появляются с явной подписью «сейчас будет корень». Они обычно скрыты внутри алгоритма. Поэтому важно научиться узнавать ситуацию, а не просто запоминать формулу.

Первый частый случай — проверка числа на простоту. Если число n делится на d, то существует парный множитель n/d. Один из них обязательно не превышает квадратного корня из n. Значит, цикл до корня полностью достаточен.

Второй случай — поиск всех делителей. Нужно найти все делители числа или посчитать их количество. Тогда удобно идти до корня. Если i делит n, добавляем i и n/i. Но если i*i = n, второй раз тот же делитель добавлять нельзя.

Третий сюжет — оптимизация перебора. Простое решение может работать правильно, но слишком долго. Корень помогает отсечь ту часть поиска, где новых результатов уже не будет. Это не магия, а здравый смысл.

Ещё один случай — проверка, является ли число полным квадратом. Здесь лучше сравнивать k*k с n, а не извлекать корень и проверять точность. Так вы избегаете проблем с вещественными числами (округления, погрешности).

Три вопроса, которые я держу в голове: ищу ли я делители числа? Проверяю ли число на простоту? Можно ли заменить полный перебор проверкой до корня? Если хотя бы на один вопрос ответ «да» — корень рядом. Он стоит за углом и делает вид, что просто проходил мимо.

Где это работает на реальном экзамене:

1. Задание 25 (обработка чисел, делители). Проверка на простоту, поиск всех делителей, подсчёт их количества — здесь оптимизация до √n критична для укладывания в лимит времени.

1. Задание 27 (эффективные алгоритмы). В задачах на перебор пар/троек понимание границ помогает отсечь лишние итерации.

Понимание, когда и как использовать корень, отделяет решение «работает на маленьких тестах» от решения «проходит все тесты ФИПИ».

Мини-инструкция: как решать задачи с корнями без паники

** изображение создано или обработано с помощью ИИ.

Начинайте не с кода, а с границы. Это звучит скучно, но именно граница цикла чаще всего решает задачу. Неправильный предел даёт неверный ответ, даже если код выглядит красиво.

Для проверки делителей используйте условие i * i <= n. Оно понятное, безопасное и не требует работы с вещественными числами. В Python math.sqrt возвращает float, а с плавающей точкой легко получить неточность на границе.

Можно применить math.isqrt(n) — функция из стандартного модуля math. Она возвращает целую часть квадратного корня. На экзамене важнее понимать идею. Если забыли про isqrt, условие i * i <= n спасёт ситуацию без импорта.

Порядок действий:

1. Определите, что именно ищет программа.

1. Проверьте, есть ли у числа пары множителей.

1. Организуйте цикл до условия i * i <= n.

1. Отдельно обработайте случай полного квадрата (i * i == n), чтобы не добавить делитель дважды.

1. Проверьте код на маленьких числах (1, 2, 4, 9, 16, 49).

Особые случаи. Число 1 — не простое, обрабатывайте отдельно. Число 2 — простое, но в цикл заходить не нужно. После проверки на 2 можно перебирать только нечётные делители (шаг 2). Это ускоряет код и делает его аккуратнее.

Мини-диалог из занятия:

— А если я поставлю range(2, int(sqrt(n)))?

— Тогда можете потерять сам корень.

— Например?

— Число 49. Семёрка не попадёт в проверку.

После этого ученики начинают уважать плюс один. Или переходят на i * i <= n. Второй вариант мне нравится больше.

Типичные ошибки, которые воруют баллы

** изображение создано или обработано с помощью ИИ.

Ошибки с корнями часто выглядят маленькими, но результат портят основательно. Хорошая новость: почти все такие промахи ловятся тестами.

Основные ошибки:

1. Забыли включить сам квадратный корень в проверку (например, остановились на int(sqrt(n)) вместо <=).

1. Дважды посчитали делитель у полного квадрата.

1. Сравнили float и int без осторожности (погрешности округления).

1. Назвали 1 простым числом.

1. Поставили цикл до n, хотя хватало корня.

1. Не проверили отрицательные и нулевые значения (если они возможны по условию).

1. Смешали поиск делителей и проверку простоты — разные задачи, разная логика.

Самая популярная ошибка — int(sqrt(n)) без включения границы. Код красиво написан, работает на малых числах. Приходит число 121 — и он спокойно объявляет его простым. Одиннадцать в этот момент смеётся где-то в углу.

Вторая боль — полный квадрат. При n = 36 и i = 6 делители совпадают. Если добавить 6 дважды, количество делителей станет неверным. Нужно проверять: если i == n // i — добавляем один раз.

Третья ошибка — вещественные вычисления. В простых школьных примерах всё выглядит нормально. При больших числах лучше не полагаться на float. Целочисленная проверка i * i <= n надёжнее.

Лишняя сложность. Ученик пишет вложенные циклы, массивы, флаги, счётчики. А задача решается одним циклом до корня. Привычка проговаривать идею вслух помогает: если объяснение длиннее кода в три раза — стоит остановиться.

Набор для быстрой проверки: 1, 2, 3, 4, 9, 16, 49, 97. Этот набор ловит много странностей. Он не заменяет полноценные тесты, но даёт хороший старт.

История с пробником и один полезный маршрут подготовки

** изображение создано или обработано с помощью ИИ.

Однажды ко мне пришёл ученик Артём после пробника. Он был уверен, что провалил задачу из-за «сложной математики». Мы открыли код. Там не было сложной математики. Там был цикл, который не доходил до корня.

Артём проверял делители числа 289. Это 17 × 17. Но range у него заканчивался раньше. Программа не проверила 17 и решила, что число простое. На лице Артёма было выражение человека, который понял шутку с опозданием на два дня.

Мы переписали условие на i * i <= n. Прогнали тесты. Ошибка исчезла. Затем я попросил его объяснить решение словами. Он сказал: «Если делитель больше корня, второй уже был меньше». Это и был момент победы.

Так я строю обучение: сначала идея, потом код, потом тесты. Не наоборот. Код без идеи похож на суп без соли — вроде еда, но радости мало.

Системный маршрут. Если нужна структура, посмотрите курс подготовки к ЕГЭ по информатике в онлайн-формате. Там удобно закрывать темы по шагам, без прыжков от корней к базам данных и обратно.

Самостоятельно тоже можно. Возьмите одну тему на день. Сегодня — делители. Завтра — простые числа. Потом — оптимизация перебора. После каждой темы решайте несколько задач и пишите короткий вывод. Не «я всё понял», а конкретно: «цикл ставлю до i * i <= n».

Через неделю такие заметки становятся личной шпаргалкой. Только честной, без мелкого шрифта на ладони. Ладонь — классика, но лучше всё-таки голова.

Хотите научиться писать код, который проходит все тесты с первого раза? В «ЕГЭленд» мы учим не просто синтаксису, а алгоритмическому мышлению: как оптимизировать перебор, избегать погрешностей и находить границы цикла. Запишитесь на онлайн-курсы по подготовке к ЕГЭ.

FAQ: короткие ответы на частые вопросы

** изображение создано или обработано с помощью ИИ.

Нужно ли учить формулу квадратного корня? Да, но без фанатизма. Для ЕГЭ по информатике важнее понимать ограничение перебора. Корень показывает, где можно остановить проверку делителей.

Что лучше: sqrt или i * i <= n? Для циклов удобнее i * i <= n. Это целочисленная проверка, она не зависит от погрешностей вещественных чисел.

Можно ли использовать math.isqrt? Да, если пишете на Python. Функция math.isqrt(n) возвращает целую часть корня. Но нужен импорт модуля math. На экзамене допустимо, если вы помните про импорт.

Почему 1 не считается простым числом? Такое число имеет ровно два натуральных делителя. У единицы только один делитель.

Как понять, что число — полный квадрат? Найдите k = math.isqrt(n), затем проверьте k * k == n. Без isqrt можно идти циклом, пока i * i не превысит n, но это медленнее.

Сколько задач решать по теме? Ориентируйтесь не на число, а на устойчивость. Если объясняете решение без подсказки — тема пошла. Если каждый раз гадаете с границей — решайте ещё.

Что делать, если на экзамене забыли функцию? Пишите простой цикл с условием i * i <= n. Это работает без специальных функций. Мой любимый аварийный выход.

Квадратные корни в ЕГЭ по информатике — не враги. Это маленький инструмент, который делает код быстрее и чище. Разберитесь с ним один раз, и многие задачи станут заметно спокойнее.