Всем привет, читатели моего блога. Недавно был разбор задачи с делителями на канале. И в комментариях меня укорили в том, что задача не решена. К сожалению, не все дочитывают статьи до конца, поэтому возникают такие комментарии. И тем не менее, я благодарен аргументированной критике. Потому что благодаря критике я вижу свои ошибки и развиваюсь.
Задача была решена, как и позапрошлая задача с делителями. Другой вопрос, что существует более оптимальный способ, который мне и подсказали в комментариях. За это я благодарен Александру. Что ж, давайте разбирать этот способ. Но для начала вспомним формулировку той самой задачи:
Задание: Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
Первый способ решения
Изначально было предложено решение полного исследования всех чисел. Но дело в том, что диапазон в условии довольно большой, поэтому задача решалась таким способом за 58 секунд. Но решалась правильно. Посмотрим на этот способ сразу через реализацию. (Более подробно описал здесь)
Время выполнения программы и результат
Второй способ решения
Суть заключается в том, что мы должны заметить, что натуральное простое число в 4 степени, например x⁴, имеет ровно 5 делителей: 1, x, x², x³, x⁴. Таким образом, если взять x нечетным, то у числа x⁴ будет ровно 5 нечетных делителей. То есть если мы возьмем простое нечетное число, возведем его в 4-ю степень, то она будет иметь только 5 нечетных делителей. Поэтому мы можем собрать произвольное число, лежащее в диапазоне [35 000 000; 40 000 000] из произведения двух частей:
1 часть: x⁴, где x - простое и нечетное число, значит лежит в диапазоне всех простых чисел от 2 до 79 (корня 4-й степени из края диапазона) (без учета 2, т.к. оно четное простое).
2 часть: 2^k , где k точно не больше 19, т.к. 2^19 * 3^4 уже превышает верхнюю границу диапазона, т.е. более 40 000 000. Домножение на коэффициент 2^k мы берем потому, что у нас может быть сколько угодно четных делителей, но среди них не должно попасть ни одного нечетного числа, потому что все 5 нечетных чисел у нас уже содержатся в x⁴.
Поэтому общий вид текущего числа из заданного диапазона будет:
current = x⁴ ⋅ 2^k , где вместо x мы перебираем все простые числа из множества {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79}. А k лежит в диапазоне 0 < k < 19. Потому что 79⁴ уже нет смысла домножать на что-то большее чем 2^0 = 1, ибо в противном случае оно выйдет за границу диапазона.
Попробую представить кратко идею решения на одной картинке:
Чтобы удобнее было перебирать x из множества простых чисел, можно воспользоваться алгоритмом фильтрации ( Решето Эратосфена ) и собрать в массиве по порядку все простые числа от 3 до 79.
Далее, четвертую степень каждого из этих простых чисел будем пытаться домножать на 2, пока оно не попадет в диапазон [35M; 40M]. Если попадает, то выписываем его. Если не попадает, то переходим к следующему.
Сложность работы такого алгоритма растет с меньшей скоростью, поэтому работать он должен быстрее.
Время выполнения программы и результат
Как мы видим, числа расположены немного в другой последовательности, но точно такие же. А вот сама программа выполняется заметно быстрее. Получается, что большие диапазоны чисел должны давать повод задуматься о том, как мы можем использовать факторизацию числа, чтобы резко сократить длину диапазона исследования. А значит и уменьшить число инструкций, чтобы ускорить программу.
Понравился разбор задачи? Проявите активность: лайк, репост, комментарий.
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram