Dado un número entero N , la tarea es verificar si la Función Totient de Euler de N y 2 * N son iguales o no. Si se encuentra que son iguales, imprima “ Sí” . De lo contrario, escriba “ No” .
Ejemplos:
Entrada: N = 9
Salida: Sí
Explicación:
Sea phi() la función Euler Totient
Dado que 1, 2, 4, 5, 7, 8 tienen MCD 1 con 9. Por lo tanto, phi(9) = 6.
Dado que 1, 5 , 7, 11, 13, 17 tienen MCD 1 con 18. Por lo tanto, phi(18) = 6.
Por lo tanto, phi(9) y phi(18) son iguales.Entrada: N = 14
Salida: No
Explicación:
Sea phi() la función Totient de Euler, luego
Como 1, 3 tienen MCD 1 con 4. Por lo tanto, phi(4) = 2.
Como 1, 3, 5, 7 tienen MCD 1 con 8. Por lo tanto, phi(8) = 4.
Por lo tanto, phi(4) y phi(8) no son lo mismo.
Enfoque ingenuo: el enfoque más simple es encontrar la función Totient de Euler de N y 2 * N. Si son iguales, escriba «Sí». De lo contrario, escriba “No”.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to find the Euler's // Totient Function int phi(int n) { // Initialize result as N int result = 1; // Consider all prime factors // of n and subtract their // multiples from result for (int p = 2; p < n; p++) { if (__gcd(p, n) == 1) { result++; } } // Return the count return result; } // Function to check if phi(n) // is equals phi(2*n) bool sameEulerTotient(int n) { return phi(n) == phi(2 * n); } // Driver Code int main() { int N = 13; if (sameEulerTotient(N)) cout << "Yes"; else cout << "No"; }
Java
// Java program of // the above approach import java.util.*; class GFG{ // Function to find the Euler's // Totient Function static int phi(int n) { // Initialize result as N int result = 1; // Consider all prime factors // of n and subtract their // multiples from result for (int p = 2; p < n; p++) { if (__gcd(p, n) == 1) { result++; } } // Return the count return result; } // Function to check if phi(n) // is equals phi(2*n) static boolean sameEulerTotient(int n) { return phi(n) == phi(2 * n); } static int __gcd(int a, int b) { return b == 0 ? a :__gcd(b, a % b); } // Driver Code public static void main(String[] args) { int N = 13; if (sameEulerTotient(N)) System.out.print("Yes"); else System.out.print("No"); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program of the # above approach # Function to find the Euler's # Totient Function def phi(n): # Initialize result as N result = 1 # Consider all prime factors # of n and subtract their # multiples from result for p in range(2, n): if (__gcd(p, n) == 1): result += 1 # Return the count return result # Function to check if phi(n) # is equals phi(2*n) def sameEulerTotient(n): return phi(n) == phi(2 * n) def __gcd(a, b): return a if b == 0 else __gcd(b, a % b) # Driver Code if __name__ == '__main__': N = 13 if (sameEulerTotient(N)): print("Yes") else: print("No") # This code is contributed by Amit Katiyar
C#
// C# program of // the above approach using System; class GFG{ // Function to find the Euler's // Totient Function static int phi(int n) { // Initialize result as N int result = 1; // Consider all prime factors // of n and subtract their // multiples from result for (int p = 2; p < n; p++) { if (__gcd(p, n) == 1) { result++; } } // Return the count return result; } // Function to check if phi(n) // is equals phi(2*n) static bool sameEulerTotient(int n) { return phi(n) == phi(2 * n); } static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver Code public static void Main(String[] args) { int N = 13; if (sameEulerTotient(N)) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by shikhasingrajput
Javascript
<script> // JavaScript program for //the above approach // Function to find the Euler's // Totient Function function phi(n) { // Initialize result as N let result = 1; // Consider all prime factors // of n and subtract their // multiples from result for (let p = 2; p < n; p++) { if (__gcd(p, n) == 1) { result++; } } // Return the count return result; } // Function to check if phi(n) // is equals phi(2*n) function sameEulerTotient(n) { return phi(n) == phi(2 * n); } function __gcd( a, b) { return b == 0 ? a :__gcd(b, a % b); } // Driver Code let N = 13; if (sameEulerTotient(N)) document.write("Yes"); else document.write("No"); // This code is contributed by souravghosh0416. </script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la observación clave es que no es necesario calcular la función Totient de Euler, ya que solo los números impares siguen la propiedad phi(N) = phi(2*N) , donde phi() es la función de Euler. Función Totiente.
Por tanto, la idea es comprobar si N es impar o no. Si es cierto, escriba «Sí». De lo contrario, escriba “No”.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to check if phi(n) // is equals phi(2*n) bool sameEulerTotient(int N) { // Return if N is odd return (N & 1); } // Driver Code int main() { int N = 13; // Function Call if (sameEulerTotient(N)) cout << "Yes"; else cout << "No"; }
Java
// Java program of the above approach class GFG{ // Function to check if phi(n) // is equals phi(2*n) static int sameEulerTotient(int N) { // Return if N is odd return (N & 1); } // Driver code public static void main(String[] args) { int N = 13; // Function call if (sameEulerTotient(N) == 1) System.out.print("Yes"); else System.out.print("No"); } } // This code is contributed by Dewanti
Python3
# Python3 program of the above approach # Function to check if phi(n) # is equals phi(2*n) def sameEulerTotient(N): # Return if N is odd return (N & 1); # Driver code if __name__ == '__main__': N = 13; # Function call if (sameEulerTotient(N) == 1): print("Yes"); else: print("No"); # This code is contributed by Amit Katiyar
C#
// C# program of // the above approach using System; class GFG{ // Function to check if phi(n) // is equals phi(2*n) static int sameEulerTotient(int N) { // Return if N is odd return (N & 1); } // Driver code public static void Main(String[] args) { int N = 13; // Function call if (sameEulerTotient(N) == 1) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by Rajput-Ji
Javascript
<script> //Javascript program of the above approach // Function to check if phi(n) // is equals phi(2*n) function sameEulerTotient(N) { // Return if N is odd return (N & 1); } // Driver Code var N = 13; // Function Call if (sameEulerTotient(N)) document.write( "Yes"); else document.write("No"); </script>
Yes
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)