Всем привет. Меня зовут Елена, и на канале TeachYOU мы разбираем темы и задачи из ЕГЭ по информатике. Изначально я планировала писать статьи по базовым темам, но этот материал будет на тему делителей числа - то, что встречается в 25м прототипе. По моему мнению, этот материал относится к разряду тех, что нужно осознать один раз и в дальнейшем просто пользоваться этими соображениями.
Пример задачи
Рассмотрим задачу 22 с сайта kompege.ru.
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.
Далее я предполагаю, что вы знакомы с принципами программирования.
Предлагаю сначала решить эту задачу "в лоб":
1) циклом перебираем числа из диапазона [174457; 174505], записываем их в переменную x.
2) для каждого числа х будем искать делители и считать их. Заведем список dels = [] - в него будем записывать делители числа x.
а) так как нам не нужно находить тривиальные делители (единицу и само число), будем искать делители среди чисел d из диапазона [2, x-1].
б) для каждого числа d проверяем, является ли оно делителем числа x (если является, то остаток от деления x на d равен нулю). Если является - добавляем делитель d в список dels.
в) после того, как перебрали все числа d - "возможные делители", проверяем количество делителей в списке dels. Если их два - выводим эти делители на экран.
3) если перебрали не все числа x, возвращаемся к п.1)
Ниже размещаю листинг кода, ссылка на программу тут.
Немного оптимизируем
Сокращение диапазона поиска возможных делителей
Рассмотрим число 12. Кроме тривиальных, его делителями являются числа 2, 3, 4, 6. Можно заметить, что его максимальный делитель равен 12 // 2. Получается, что возможные делители числа x находятся в диапазоне [2; x // 2] (здесь // - обозначает операцию целочисленного деления - взятия целой части от деления). Давайте изменим этот момент в коде и посмотрим, как меняется время выполнения программы:
Введение функции break
Также можно отметить, что если в списке dels уже есть три делителя, дальше проверять, являются ли числа d делителями, бессмысленно - все равно данное число x не подходит для ответа (ищем числа с двумя нетривиальными делителями). Поэтому можно прервать цикл по возможным делителям с помощью оператора досрочного выхода из цикла break.
Такая небольшая оптимизация позволила нам ускорить программу почти в десять раз!
Интересное о делителях
Для дальнейшей оптимизации нужно узнать/осознать/вспомнить кое-что о делителях.
Еще раз рассмотрим число 12 и его делители:
Делаем вывод, что, если у числа x четное количество делителей n, то, зная первые (минимальные) n // 2 делителей, можем найти его оставшиеся делители как частное от числа x и его известных делителей.
Появляются вопросы:
- Где проходит граница диапазона для поиска минимальных делителей?
- А что, если у числа нечетное количество делителей?
Начнем со второго вопроса.
Рассмотрим делители числа 16:
Как и следовало ожидать, если количество делителей нечетно - один из них будет непарным. Но на самом деле он парен самому себе: 4*4 = 16.
Делаем важный вывод. У числа x будет нечетное количество делителей тогда и только тогда, когда есть число y, такое, что y * y = x. Другими словами, если число является квадратом другого числа, у него нечетное количество делителей (и наоборот).
И вывод (или замечание) второе - граница поиска минимального делителя числа x проходит по значению корня из числа х.
Получается, что процедуру поиска делителей числа x можно разбить на части:
- Вычисление границы диапазона поиска наименьших делителей.
- Поиск наименьших делителей в этом диапазоне.
- Если в задаче нужно определить количество делителей - умножаем количество наименьших делителей на два. Если нужно напрямую вычислить делители - находим их как частное от деления числа x на известные делители.
- Если число является полным квадратом - добавляем этот делитель в список уже найденных (или увеличиваем количество делителей на единицу).
Звучит логично и несложно, но на самом деле определение, является ли число полным квадратом, не такая простая задача из-за погрешности вычислений. Этот момент оставим пока в стороне и вернемся к задаче поиска чисел с двумя нетривиальными делителями.
Окончательная оптимизация
Изменим программу, приведенную выше.
Во-первых, будем добавлять в список делитель d и сразу его пару x // d.
Во-вторых, уменьшим диапазон для поиска наименьших делителей d. Следует отметить, что есть разные пути реализации диапазона (кстати, мы не можем просто взять диапазон [2, round(x ** 0.5)] - если интересно, проверьте, в каких границах будете искать делители для чисел 12, 15, 16). Я предлагаю взять диапазон с запасом, например, [2, round(x ** 0.5) + 1] и добавить проверку - если делитель в квадрате равен числу x, то в список делителей добавляем его без пары; если квадрат делителя больше числа x - делаем break. Такая реализация будет достаточно строгой - мы точно переберем все нужные числа и не посчитаем какие-то делители дважды.
Программу можете найти по ссылке здесь. Листинг привожу на картинке.
Обратите внимание на время выполнения программы! В сравнении с исходными 1.03 секундами мы ускорились в 600 раз! Эта разница будет особенно заметна в задачах с большими числами.
Задача на поиск чисел с нечетным количеством делителей
Задача 67 с компегэ:
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [81234; 134689], числа, имеющие ровно три различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти три делителя в таблицу на экране с новой строки в порядке возрастания этих трех делителей. Делители в строке таблицы также должны следовать в порядке возрастания.
Итак, если у числа нечетное количество делителей - оно является квадратом. Такую задачу можно решать как минимум двумя способами:
- Перебирать числа из диапазона, данного в условии. Выбирать те, что являются квадратами, и для них считать делители.
- Понять, в каком диапазоне лежат корни чисел из условия. Перебирать именно их. Для каждого корня k определяем число x = k * k и ищем его делители среди чисел [2, k).
Предлагаю решать задачу вторым способом - он обещает быть производительнее.
- Корень из 81234 = 285,0157...
- Корень из 134689 = 367
Значит, диапазон перебора чисел k равен [286, 367]. Программу можно посмотреть и запустить тут.
Несмотря на то, что это базовая задачка, время выполнения не может не радовать.
Надеюсь, этот материал был вам интересен и полезен. Буду признательна обратной связи в виде лайков и комментариев.
Я очень люблю 25 номера из ЕГЭ по информатике) Если интересно разобрать задачи с масками или с делителями, но более сложные - отметьтесь в комментариях, и я напишу такую статью.