Рассмотрим решение задачи на простые числа, так как это одна из самых распространённых тем в олимпиадном программировании. Читаем условие задачи:
Давайте сначала напишем функцию, которая проверяет, является ли число простым. Напомню определение простого числа:
Простое число — это натуральное число, имеющее ровно два различных натуральных делителя.
Иначе говоря, натуральное число a является простым, если оно отлично от 1 и делится без остатка только на 1 и на самого себя. Таким образом, необходимо проверить делимость числа a на все числа от 2 до a (не включая).
Однако такой вариант решения работает слишком долго. И нам понадобится немного математики. Предположим, что число a не простое, тогда существуют такие b и c, что a = b * c. Без потери общности можно считать, что b <= c. Тогда можно показать, что b * b <= a (или другими словами, что b не превосходит квадратного корня из a).
Тогда мы приходим к тому, что можно проверять не все числа до a, а все числа до квадратного корня из a. Можем писать код:
В цикле же делаем очень простое действие - проверяем остаток от деления:
Если у числа найдётся хоть один делитель, тогда выполнение функции прекратится и вернётся False. Если же цикл закончит выполнение, то значит, что число простое:
Важное замечание, что эта функция не обрабатывает единицу, поэтому для использования в общем случае надо будет ещё написать одно условие. Но в нашем случае это не нужно, поэтому оставлю это на самостоятельную работу.
Теперь можем приступить к решению задачи. Считаем число:
Осталось пройтись по всем числам из интервала (n, 2 * n) и вызвать написанную нами функцию. Для каждого числа функция вернёт True или False, и надо просуммировать эти значения:
Получилось довольно развёрнутое решение. Но теперь мы вооружились универсальной функцией, которую можно будет использовать во множестве других решений.
Предыдущий выпуск: Задача 79. Последняя цифра A^B
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.