Maximum GCD of N integers with given product | Python3 implementation of above approach ; Function to find maximum GCD of N integers with product P ; map to store prime factors of P ; prime factorization of P ; traverse all prime factors and multiply its 1 / N power to the result ; Driver code
from math import sqrt NEW_LINE def maxGCD ( N , P ) : NEW_LINE INDENT ans = 1 NEW_LINE prime_factors = { } NEW_LINE for i in range ( 2 , int ( sqrt ( P ) + 1 ) ) : NEW_LINE INDENT while ( P % i == 0 ) : NEW_LINE INDENT if i not in prime_factors : NEW_LINE INDENT prime_factors [ i ] = 0 NEW_LINE DEDENT prime_factors [ i ] += 1 NEW_LINE P //= i NEW_LINE DEDENT DEDENT if ( P != 1 ) : NEW_LINE INDENT prime_factors [ P ] += 1 NEW_LINE DEDENT for key , value in prime_factors . items ( ) : NEW_LINE INDENT ans *= pow ( key , value // N ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N , P = 3 , 24 NEW_LINE print ( maxGCD ( N , P ) ) NEW_LINE DEDENT