Высота факторного дерева для заданного числа

Учитывая положительное целое число N , задача состоит в том, чтобы найти высоту Факторного Дерева данного целого числа N .

Примеры:

Input: N = 20
Output: 3
Explaination: The height of the Factor Tree of 20 shown in the image below is 3.

Input: N = 48
Output: 5

Подход: Данная проблема может быть решена с помощью шагов, описанных ниже:

• Инициализируйте переменную, скажем, height как 0 , которая хранит высоту Факторного Дерева данного целого числа N .
• Переберите все значения i в диапазоне [2, √N] и выполните следующие шаги:
  1. Найдите наименьший делитель числа N и, если он существует, увеличьте значение высоты на 1 .
  2. Если делитель i существует, повторите описанный выше шаг, обновив значение N до N/i , пока N > 1 .
  3. Если делителей числа N не существует, цикл разорвется.
• После выполнения вышеуказанных шагов выведите значение высоты в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(√N*log N)
Вспомогательное пространство: O(1)