Мне кажется, Вы новичок в спортивном программировании, т.к. придаете своему алгоритму слишком большое значение. Он работает быстро лишь для частных случаев, где простые делители числа малы. Попробуйте свой алгоритм на простом числе. Попробуйте на произведении двух простых чисел порядка 10^25. Видите разницу? Естественно, можно такой алгоритм запустить и на 72576 * 10 ^ 50 запустить, потому что он быстро найдет делители по типу двойки и пятерки, а после деления на них число для дальнейшего поиска вообще крохотное.
P.S. Очень редко когда очевидный алгоритм, лежащий на поверхности, оказывается во много раз более оптимальным. Здесь два варианта - либо он не решает задачу, либо решает для каких-то специфических случаев :)
Но вообще идея деления на простой делитель после его нахождения очень хороша, хотя и не нова. Удачи и успехов в дальнейшем изучении, у Вас хорошо получается ;)
Написано
Войдите на сайт
Чтобы задать вопрос и получить на него квалифицированный ответ.
Спасибо, что подсказали насчет остальных оптимизаций!