Given an integer N, the task is to check whether the Euler’s Totient Function of N and 2 * N are the same or not. If they are found to be the same, then print “Yes”. Otherwise, print “No”.
Examples:
Input: N = 9
Output: Yes
Explanation:
Let phi() be the Euler Totient function
Since 1, 2, 4, 5, 7, 8 have GCD 1 with 9. Therefore, phi(9) = 6.
Since 1, 5, 7, 11, 13, 17 have GCD 1 with 18. Therefore, phi(18) = 6.
Therefore, phi(9) and phi(18) are equal.Input: N = 14
Output: No
Explanation:
Let phi() be the Euler Totient function, then
Since 1, 3 have GCD 1 with 4. Therefore, phi(4) = 2.
Since 1, 3, 5, 7 have GCD 1 with 8. Therefore, phi(8) = 4.
Therefore, phi(4) and phi(8) are not the same.
Naive Approach: The simplest approach is to find Euler’s Totient Function of N and 2 * N. If they are the same, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the Euler's// Totient Functionint 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 Codeint main(){ int N = 13; if (sameEulerTotient(N)) cout << "Yes"; else cout << "No";} |
Java
// Java program of // the above approachimport java.util.*;class GFG{// Function to find the Euler's// Totient Functionstatic 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 Codepublic 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 Functiondef 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 Codeif __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 approachusing System;class GFG{// Function to find the Euler's// Totient Functionstatic 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 Codepublic 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 Functionfunction 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
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the key observation is that there is no need to calculate the Euler’s Totient Function as only odd numbers follow the property phi(N) = phi(2*N), where phi() is the Euler’s Totient Function.
Therefore, the idea is to check if N is odd or not. If found to be true, print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
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 Codeint main(){ int N = 13; // Function Call if (sameEulerTotient(N)) cout << "Yes"; else cout << "No";} |
Java
// Java program of the above approachclass 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 codeif __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 approachusing 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 Codevar N = 13;// Function Callif (sameEulerTotient(N)) document.write( "Yes");else document.write("No");</script> |
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)
