Задание:
Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
Решение:
Нужные делители будем искать методом перебора, который немного оптимизируем так, чтобы проход был не от 1 до ТЕКУЩЕГО_ЧИСЛА, а до корня из текущего числа. Так как, если мы знаем делитель division до корня, то легко найти парный делитель, лежащий после корня: pair_division := x div division; где x - это текущее число, делители которого ищутся.
Тогда основное тело программы можно записать довольно компактно и просто:
x_start - начало диапазона поиска, x_end - конец диапазона.
Для каждого числа current из этого диапазона мы проверяем, есть ли у него 5 различных нечетных делителей. Если да, то выводим его на экран.
Теперь реализация функции countOddDivisions() :
В этой функции для оптимизации сделано следующее. Если мы находим 6 нечетных делителей, то это уже нам не подходит, поэтому дальнейшие вычисления прерываются и функция возвращает 6, даже если там может быть еще намного больше делителей. Это нужно для более быстрого решения конкретно в этой задаче.
Заводим счетчик делителей count. Сначала высчитывается корень из числа с отбрасыванием дробной части root := trunc(sqrt(x)); Далее пробегаем от 1 до root. Если находим число, на которое делится число x, то division является делителем числа x. Если он нечетный, то увеличиваем счетчик на 1. Далее находим парный делитель pair_division, лежащий за root. (от root до x).
Если этот парный делитель pair_division тоже нечетный и не совпадает с делителем исходным division (с которым он стоит в паре, что может быть только для чисел, являющихся квадратом натурального числа), тогда увеличиваем счетчик еще на 1.
В конце возвращаем результат, который колеблется от 0 до 6. После 6 нечетных делителей не считаем дальше для ускорения работы программы. Количество четных делителей не играет роли.
Возможно, вы помните, что в прошлый раз была более сложная задача из ЕГЭ по информатике по теме делителей. Время выполнения таких программ на больших диапазонах может быть существенно больших. Поэтому по возможности, нужно стараться оптимизировать программу.
Как оптимизировать программы | Разбор задачи из ЕГЭ по информатике
Разбор 26 задачи ЕГЭ по информатике: серьезный подвох
Понравился разбор задачи? Проявите активность: лайк, репост, комментарий.
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram