Maximum GCD of N integers with given product | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxGCD ( int N , int P ) { int ans = 1 ; unordered_map < int , int > prime_factors ; for ( int i = 2 ; i * i <= P ; i ++ ) { while ( P % i == 0 ) { prime_factors [ i ] ++ ; P /= i ; } } if ( P != 1 ) prime_factors [ P ] ++ ; for ( auto v : prime_factors ) ans *= pow ( v . first , v . second / N ) ; return ans ; } int main ( ) { int N = 3 , P = 24 ; cout << maxGCD ( N , P ) ; return 0 ; }