Maximum GCD of N integers with given product in C++

Suppose we two integers N and P. The P is the product of N unknown integers. We have to find the maximum possible GCD of those integers. Suppose N = 3, and P = 24, then different groups will be like {1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2, 2, 6}, {2, 3, 4}. The GCDs are: 1, 1, 1, 1, 2, 1. So answer is 2 here.

We will find all prime factors of P, and store them into hashmap. The N integers will have max GCD when the prime factor will be common in all the integers. So if P = p₁^k1 * p₂^k2 * … * p_n^kn. Here pi is the prime factor. Then max GCD will be res = p₁^k1/N * p₂^k2/N * … * p_n^kn/N.

Example

 Live Demo

#include <iostream> #include <cmath> #include <unordered_map> using namespace std; long getMaxGCD(long N, long p) {    int gcd = 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)       gcd = gcd * pow(v.first, v.second / N);    return gcd; } int main() {    long n = 3;    long p = 24;    cout << "MAX GCD: " << getMaxGCD(n, p); }

Output

MAX GCD: 2