Maximum GCD from Given Product of Unknowns | 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
< ? php function max_gcd ( $ n , $ p ) { $ count = 0 ; $ gcd = 1 ; while ( $ p % 2 == 0 ) { $ p >>= 1 ; $ count ++ ; } if ( $ count > 0 ) $ gcd *= pow ( 2 , ( int ) ( $ count / $ n ) ) ; for ( $ i = 3 ; $ i <= ( int ) sqrt ( $ p ) ; $ i += 2 ) { $ count = 0 ; while ( $ p % $ i == 0 ) { $ count ++ ; $ p = ( int ) ( $ p / $ i ) ; } if ( $ count > 0 ) { $ gcd *= pow ( $ i , ( int ) ( $ count / $ n ) ) ; } } if ( $ p > 2 ) $ gcd *= pow ( $ p , ( int ) ( 1 / $ n ) ) ; return $ gcd ; } $ n = 3 ; $ p = 80 ; echo ( max_gcd ( $ n , $ p ) ) ;