Задача
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.
Например, в диапазоне [5; 16] ровно три различных натуральных делителя имеет число 16, поэтому для этого диапазона вывод на экране должна содержать следующие значения: 16 8
Решение
Введение в суть проблемы
В некоторых хороших книгах по разработке пишут, что код должен быть простой и понятный. А значит задача должна разбиваться на маленькие подзадачи, каждую из которых выполняет свой отдельный метод/функция/процедура.
И это правильный хороший подход, но иногда он может привести вас к алгоритмической ошибке, точнее завести вашу программу в узкое место. В результате код может быть понятный, но настолько медленный, что бесполезный.
Давайте рассмотрим как это получается на практике. Вернемся к нашей задаче. Нам нужно выписать все числа, имеющие ровно 3 делителя, из заданного диапазона, при этом с каждым числом написать его максимальный делитель.
Наивный алгоритм
1. Написать функцию для нахождения количества всех делителей.
2. Написать функцию для нахождения максимального делителя.
3. Написать функцию, которая пройдется по всем числам диапазона и в зависимости от количества делителей, если оно равном трем, будет выдавать текущее число и его максимальный делитель.
Замечания к наивному алгоритму
1. Функция, делающая полный перебор всех чисел от 2 до x - 1, чтобы найти количество делителей числа x не оптимальна. Так как у каждого делителя есть своя пара, то пройтись можно до округленного (или до целой части) корня из числа x. Это уже сократит количество инструкций.
Здесь стоит заметить, что у чисел, которые являются квадратами, т. е. корень из которых дает целое число, имеется нечетное количество делителей, потому что два делителя около середины числа вырождаются в один, который совпадает с корнем числа. А у чисел, которые квадратами не являются, всегда четное количество делителей.
Проверить является ли числом квадратом можно сравнив его корень с целой частью от взятия корня. Для нашего случая 3 делителя будет иметь только то число, которое является квадратом, так как 3 - нечетное.
Написать отдельную функцию, проверяющую наличие 3 делителей можно следующим образом:
2. Написать функцию для нахождения максимального делителя можно по-разному. Можно пойти с конца, начиная с (x - 1) до 2, и как только поделится нацело, то сразу же сделать break. Но будет ли это оптимально? Нет. Более того, для больших чисел подход с делением, начиная с конца, может еще оказаться медленным. Давайте вспомним про то, что каждый большой делитель с конца имеет свою пару в виде маленького делителя в начале. Так почему бы не найти первый маленький делитель и сразу же найти максимальный с помощью целочисленного деления x div division (Pascal) или (int) x / (int) division (C/C++) или x // division (Python). Отдельная реализация такой функции может выглядеть так:
3. Тогда нам остается собрать всё это вместе в какую-то общую процедуру решения (solution) и написать что-то вроде следующего:
Соберем это всё вместе:
И всё было бы хорошо, код рабочий, показывает правильные результаты, вроде даже быстро выдает ответ. НО! Пока используешь маленький диапазоны.
А что если нам задан диапазон чисел, который еле в integer влезает? Вот если запустить эту программу с диапазоном, который задан в условии задачи, то ответа можно ждать долго. Даже на довольно современном процессоре.
Что делать?
Вот тут как раз против нас сыграла то, что мы сделали программу модульной там, где это не нужно. В конечной функции solution у нас спрятано от глаз 3 вложенных цикла for, хотя на самом деле можно было обойтись двумя, если поиск количество делителей в числе объединить с поиском максимального делителя, не упуская шанс убить двух зайцев во время одного запуска цикла for, вместо того, чтобы плодить циклы.
Если же теперь всё написать в общем коде, без разбиения на функции, то получится так:
Комментарии по сложным моментам кода:
Line 15 - проверяем, является ли число квадратом, чтобы знать четное количество делителей у него или нет.
Line 16 - учитываем тот самый делитель, который корень (далее его не учитываем, т. к. пары у него не будет )
Line 17 - предположительно максимальный делитель
Line 19 - проходим от 2-ки до корня из числа (не включая последний)
Line 21 - если на какое-то число поделилось нацело, то один раз пересчитываем макс. дел. по его минимальному делителю.
Line 22 - если у текущего числа x насчитается уже больше 3 делителей, то не имеет смысла считать дальше, так как нам это число уже не подойдет в любом случае.
Line 23 - так как у каждого делителя, находящегося до sqrt(x) есть парный делитель, находящийся после sqrt(x), то добавляем сразу 2 к счетчику, чтобы учесть оба.
Да, код получается сложнее, но работает уже в 2 раза быстрее, по сравнению с предыдущей версией.
Что можно придумать еще для ускорения задачи?
1. В условном выражении (проверка числа на квадрат) корень вычисляется 2 раза. Можно вычислить корень заранее, а потом уже его использовать. Это немного ускорит программу. Но не сильно.
2. Если еще немного посмотреть на числа, то можно заметить, что 3 делителя имеют только четвертые степени простых чисел.
Получается, что мы можем заметно ускорить нашу программу, если возьмем целые части у корней 4-й степени от границ диапазона и пройдемся в новом урезанном диапазоне в поиске простых чисел. Если таковые найдутся, то исходное число из большого диапазона можно будет получить возведением в 4-ю степень, а максимальный делитель - возведением в 3-ю степень. Такая программа будет отрабатывать мгновенно, в отличие от предыдущей версии. Хотя все версии программы работают верно.
Пример работы программы:
Вывод
Не всегда нужно разделять логику программы на блоки, на процедуры и функции, потому что в таком случае вы можете запускать два цикла для нахождения двух параметров, которые можно было сразу найти в одном цикле. А потеря времени выполнения программы всегда неприятна. Всегда нужно искать альтернативное решение с более маленькими диапазонами данных. А для этого приходится взять черновик и, набросав несколько примеров, посмотреть на зависимости. Экспериментировать и не бояться ошибаться.
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram
