Check all the possible numbers that can divide p
for ( long i = 3 ; i <= sqrt ( p ) ; i += 2 ) { count = 0 ; while ( p % i == 0 ) { count ++ ; p = p / i ; } if ( count > 0 ) { gcd *= ( long ) pow ( i , count / n ) ; } }