Count ways to represent an integer as an exponent | Python3 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 math NEW_LINE def gcd ( a , b ) : NEW_LINE INDENT while ( b > 0 ) : NEW_LINE INDENT rem = a % b NEW_LINE a = b NEW_LINE b = rem NEW_LINE DEDENT return a NEW_LINE DEDENT def countNumberOfWays ( n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT g = 0 NEW_LINE power = 0 NEW_LINE while ( n % 2 == 0 ) : NEW_LINE INDENT power += 1 NEW_LINE n //= 2 NEW_LINE DEDENT g = gcd ( g , power ) NEW_LINE for i in range ( 3 , int ( math . sqrt ( g ) ) + 1 , 2 ) : NEW_LINE INDENT power = 0 NEW_LINE while ( n % i == 0 ) : NEW_LINE INDENT power += 1 NEW_LINE n //= i NEW_LINE DEDENT g = gcd ( g , power ) NEW_LINE DEDENT if ( n > 2 ) : NEW_LINE INDENT g = gcd ( g , 1 ) NEW_LINE DEDENT ways = 1 NEW_LINE power = 0 NEW_LINE while ( g % 2 == 0 ) : NEW_LINE INDENT g //= 2 NEW_LINE power += 1 NEW_LINE DEDENT ways *= ( power + 1 ) NEW_LINE for i in range ( 3 , int ( math . sqrt ( g ) ) + 1 , 2 ) : NEW_LINE INDENT power = 0 NEW_LINE while ( g % i == 0 ) : NEW_LINE INDENT power += 1 NEW_LINE g /= i NEW_LINE DEDENT ways *= ( power + 1 ) NEW_LINE DEDENT if ( g > 2 ) : NEW_LINE INDENT ways *= 2 NEW_LINE DEDENT return ways NEW_LINE DEDENT N = 64 NEW_LINE print ( countNumberOfWays ( N ) ) NEW_LINE