C++ में दिए गए उत्पाद के साथ N पूर्णांकों की अधिकतम GCD

मान लीजिए कि हम दो पूर्णांक N और P हैं। P, N अज्ञात पूर्णांकों का गुणनफल है। हमें उन पूर्णांकों का अधिकतम संभव GCD ज्ञात करना है। मान लीजिए एन =3, और पी =24, तो अलग-अलग समूह होंगे जैसे {1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2 , 2, 6}, {2, 3, 4}। जीसीडी हैं:1, 1, 1, 1, 2, 1. तो उत्तर यहां 2 है।

हम P के सभी अभाज्य गुणनखंडों को खोजेंगे, और उन्हें हैशमैप में संग्रहित करेंगे। N पूर्णांकों में अधिकतम GCD होगा जब सभी पूर्णांकों में अभाज्य गुणनखंड उभयनिष्ठ होगा। तो अगर पी =पी<उप>1 ^k1 * पी<उप>2 ^k2 * ... * पी<उप>एन ^kn . यहां पाई प्रमुख कारक है। तब अधिकतम GCD होगा res =p₁ ^k1/N * पी<उप>2 ^k2/N * ... * पी<उप>एन ^kn/N ।

उदाहरण

#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);
}

आउटपुट

MAX GCD: 2