Suma de Funciones de Euler Totient obtenidas para cada divisor de N

Dado un entero positivo N , la tarea es encontrar la suma de la función de Euler Totient para todos los divisores del número dado N .

Ejemplos:

Entrada: N = 3
Salida: 3
Explicación:
Los divisores de 3 son {1, 3}. La función totient de Euler para los valores 1 y 3 son 1 y 2 respectivamente.
Por lo tanto, la suma requerida es 1 + 2 = 3.

Entrada: N = 6
Salida: 6

Enfoque ingenuo: el problema dado se puede resolver encontrando todos los divisores de N y luego imprimiendo la suma de los valores de la función totient de Euler para cada divisor como resultado. 

Complejidad de tiempo: O(N * sqrt(N))
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la propiedad de la función de tociente de Euler, que establece que la suma de todos los valores de la función de tociente de Euler de todos los divisores es N .

Por lo tanto, la suma de todos los valores de la función totient de Euler de N es el número mismo.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to find the sum of Euler
// Totient Function of divisors of N
int sumOfDivisors(int N)
{
    // Return the value of N
    return N;
}
 
// Driver Code
int main()
{
    int N = 5;
    cout << sumOfDivisors(N);
 
    return 0;
}

// Java program for the above approach
public class GFG {
 
    // Function to find the sum of Euler
    // Totient Function of divisors of N
    static int sumOfDivisors(int N)
    {
        // Return the value of N
        return N;
    }
    // Driver code
    public static void main(String[] args)
    {
        int N = 5;
        System.out.println(sumOfDivisors(N));
    }
}
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to find the sum of Euler
# Totient Function of divisors of N
def sumOfDivisors(N):
     
    # Return the value of N
    return N
 
# Driver Code
if __name__ == '__main__':
     
    N = 5
     
    print (sumOfDivisors(N))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
     
  // Function to find the sum of Euler
    // Totient Function of divisors of N
    static int sumOfDivisors(int N)
    {
        // Return the value of N
        return N;
    }
 
// Driver code
static void Main()
{
     int N = 5;
     Console.Write(sumOfDivisors(N));
     
}
}
 
// This code is contributed by sanjoy_62.

<script>
  
// Js program for the above approach
  
    // Function to find the sum of Euler
    // Totient Function of divisors of N
    function sumOfDivisors(N){
 
        // Return the value of N
        return N;
    }
 
    // Driver Code
    let N = 5;
    document.write(sumOfDivisors(N));
  
</script>

5

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)