MCD máximo de N enteros con producto dado

Dados N enteros con valores desconocidos (a _i > 0) que tienen producto P. La tarea es encontrar el máximo común divisor posible de estos N enteros.
Ejemplos: 
 

Input : N = 3, P = 24
Output : 2
The integers will have maximum GCD of 2 when a1 = 2, a2 = 2, a3 = 6.

Input : N = 2, P = 1
Output : 1
Only possibility is a1 = 1 and a2 = 1.

Acercarse: 
 

• Primero encuentre todos los factores primos del producto P y guárdelo en un Hashmap.
• Los N enteros tendrán MCD máximo cuando un factor primo sea común en todos los enteros.
• Entonces si P = p1 ^k1 * p2 ^k2 * p3 ^k3 …. donde p1, p2… son números primos entonces, el MCD máximo que se puede obtener será ans = p1 ^{k1 / N} * p2 ^{k2 / N} * p3 ^{k3 / N} …. 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum GCD
// of N integers with product P
int maxGCD(int N, int P)
{
 
    int ans = 1;
 
    // map to store prime factors of P
    unordered_map<int, int> prime_factors;
 
    // prime factorization of P
    for (int i = 2; i * i <= P; i++) {
 
        while (P % i == 0) {
 
            prime_factors[i]++;
 
            P /= i;
        }
    }
 
    if (P != 1)
        prime_factors[P]++;
 
    // traverse all prime factors and
    // multiply its 1/N power to the result
    for (auto v : prime_factors)
        ans *= pow(v.first, v.second / N);   
 
    return ans;
}
 
// Driver code
int main()
{
    int N = 3, P = 24;
 
    cout << maxGCD(N, P);
 
    return 0;
}

// Java implementation of above approach
import java.util.*;
class Solution
{
// Function to find maximum GCD
// of N integers with product P
static int maxGCD(int N, int P)
{
 
    int ans = 1;
 
    // map to store prime factors of P
    Map<Integer, Integer> prime_factors = 
                        new HashMap< Integer,Integer>();
 
    // prime factorization of P
    for (int i = 2; i * i <= P; i++) {
 
        while (P % i == 0) {
 
            if(prime_factors.get(i)==null)
            prime_factors.put(i,1);
            else
            prime_factors.put(i,(prime_factors.get(i)+1));
             
 
            P /= i;
        }
    }
 
    if (P != 1)
            if(prime_factors.get(P)==null)
            prime_factors.put(P,1);
            else
            prime_factors.put(P,(prime_factors.get(P)+1));
 
    // traverse all prime factors and
    // multiply its 1/N power to the result
        Set< Map.Entry< Integer,Integer> > st = prime_factors.entrySet();   
   
       for (Map.Entry< Integer,Integer> me:st)
       {
            
        ans *= Math.pow(me.getKey(),me.getValue() / N);   
        }
 
    return ans;
}
 
// Driver code
public static void main(String args[])
{
    int N = 3, P = 24;
 
    System.out.println( maxGCD(N, P));
 
}
}
//contributed by Arnab Kundu

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

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG
{
     
// Function to find maximum GCD
// of N integers with product P
static int maxGCD(int N, int P)
{
 
    int ans = 1;
 
    // map to store prime factors of P
    Dictionary<int, int> prime_factors =
                        new Dictionary< int,int>();
 
    // prime factorization of P
    for (int i = 2; i * i <= P; i++)
    {
 
        while (P % i == 0)
        {
 
            if(!prime_factors.ContainsKey(i))
                prime_factors.Add(i, 1);
            else
            prime_factors[i] = prime_factors[i] + 1;
             
            P /= i;
        }
    }
 
    if (P != 1)
            if(!prime_factors.ContainsKey(P))
                prime_factors.Add(P, 1);
            else
            prime_factors[P] = prime_factors[P] + 1;
 
    // traverse all prime factors and
    // multiply its 1/N power to the result
    foreach(KeyValuePair<int, int> me in prime_factors)
    {
             
        ans *= (int)Math.Pow(me.Key,me.Value / N);
    }
 
    return ans;
}
 
// Driver code
public static void Main(String []args)
{
    int N = 3, P = 24;
 
    Console.WriteLine( maxGCD(N, P));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
// Javascript implementation of above approach
 
 
// Function to find maximum GCD
// of N integers with product P
function maxGCD(N, P) {
 
    let ans = 1;
 
    // map to store prime factors of P
    let prime_factors = new Map();
 
    // prime factorization of P
    for (let i = 2; i * i <= P; i++) {
 
        while (P % i == 0) {
 
            if (prime_factors.get(i) == null)
                prime_factors.set(i, 1);
            else
                prime_factors.set(i, (prime_factors.get(i) + 1));
            P = Math.floor(P / i);
        }
    }
 
    if (P != 1)
        prime_factors[P]++;
 
    // traverse all prime factors and
    // multiply its 1/N power to the result
    console.log(prime_factors)
    for (let v of prime_factors) {
        console.log(v)
        ans *= Math.pow(v[0], Math.floor(v[1] / N));
    }
 
    return ans;
}
 
// Driver code
 
let N = 3, P = 24;
 
document.write(maxGCD(N, P));
 
// This code is contributed by gfgking
</script>

2