Maximum GCD from Given Product of Unknowns | Python3 implementation of the approach ; Function to return the required gcd ; Count the number of times 2 divides p ; Equivalent to p = p / 2 ; ; If 2 divides p ; Check all the possible numbers that can divide p ; If n in the end is a prime number ; Return the required gcd ; Driver code
import math NEW_LINE def max_gcd ( n , p ) : NEW_LINE INDENT count = 0 ; NEW_LINE gcd = 1 ; NEW_LINE while ( p % 2 == 0 ) : NEW_LINE INDENT p >>= 1 ; NEW_LINE count = count + 1 ; NEW_LINE DEDENT if ( count > 0 ) : NEW_LINE INDENT gcd = gcd * pow ( 2 , count // n ) ; NEW_LINE DEDENT for i in range ( 3 , ( int ) ( math . sqrt ( p ) ) , 2 ) : NEW_LINE INDENT count = 0 ; NEW_LINE while ( p % i == 0 ) : NEW_LINE INDENT count = count + 1 ; NEW_LINE p = p // i ; NEW_LINE DEDENT if ( count > 0 ) : NEW_LINE INDENT gcd = gcd * pow ( i , count // n ) ; NEW_LINE DEDENT DEDENT if ( p > 2 ) : NEW_LINE INDENT gcd = gcd * pow ( p , 1 // n ) ; NEW_LINE DEDENT return gcd ; NEW_LINE DEDENT n = 3 ; NEW_LINE p = 80 ; NEW_LINE print ( max_gcd ( n , p ) ) ; NEW_LINE