Count ways to represent an integer as an exponent | Java program for the above approach ; Function to calculate GCD of a and b using Euclidean Algorithm ; Iterate until b is non - zero ; Return the GCD ; Function to count the number of ways N can be expressed as x ^ y ; Base Case ; Stores the gcd of powers ; Calculate the degree of 2 in N ; Calculate the degree of prime numbers in N ; Calculate the degree of prime ' i ' in N ; If N is a prime , g becomes 1. ; Stores the number of ways to represent N as x ^ y ; Find the number of Factors of g ; Update the count of ways ; Iterate to find rest of the prime numbers ; Find the power of i ; Update the count of ways ; If g is prime ; Return the total number of ways ; Driver Code
import java . util . * ; class GFG { static int gcd ( int a , int b ) { while ( b > 0 ) { int rem = a % b ; a = b ; b = rem ; } return a ; } static int countNumberOfWays ( int n ) { if ( n == 1 ) return - 1 ; int g = 0 ; int power = 0 ; while ( n % 2 == 0 ) { power ++ ; n /= 2 ; } g = gcd ( g , power ) ; for ( int i = 3 ; i <= ( int ) Math . sqrt ( n ) ; i += 2 ) { power = 0 ; while ( n % i == 0 ) { power ++ ; n /= i ; } g = gcd ( g , power ) ; } if ( n > 2 ) g = gcd ( g , 1 ) ; int ways = 1 ; power = 0 ; while ( g % 2 == 0 ) { g /= 2 ; power ++ ; } ways *= ( power + 1 ) ; for ( int i = 3 ; i <= ( int ) Math . sqrt ( g ) ; i += 2 ) { power = 0 ; while ( g % i == 0 ) { power ++ ; g /= i ; } ways *= ( power + 1 ) ; } if ( g > 2 ) ways *= 2 ; return ways ; } public static void main ( String [ ] args ) { int N = 64 ; System . out . print ( countNumberOfWays ( N ) ) ; } }