Сумма функций Эйлера Тотиента, полученных для каждого делителя N

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

Примеры:

Input: N = 3
Output: 3
Explanation:
Divisors of 3 are {1, 3}. The Euler totient function for the values 1 and 3 are 1 and 2 respectively.
Therefore, the required sum is 1 + 2 = 3.

Input: N = 6
Output: 6

Наивный подход: Данную задачу можно решить, найдя все делители N и выведя в результате сумму значений функции Эйлера для каждого делителя.

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

Эффективный подход . Вышеупомянутый подход также можно оптимизировать, используя свойство общей функции Эйлера, которое гласит, что сумма всех значений общей функции Эйлера всех делителей равна N .

Следовательно, сумма всех значений эйлеровой функции N является самим числом.

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

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