मान लीजिए कि हम दो पूर्णांक 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 है।
जिस तकनीक को हम पसंद करते हैं, मान लीजिए कि g एक1 . का GCD है , एक<उप>2 , ... an . तब a, g का गुणज है, और P है (a1 * ए<उप>2 * ... * एक<उप>एन ) g n . का गुणज होना चाहिए . उत्तर अधिकतम g ऐसा है कि g n mod P =0. अब मान लीजिए P =k1 p1 * k2 p1 * ... * kn pn . g इस प्रकार का होना चाहिए, फिर g को अधिकतम करने के लिए, हमें pi . चुनना होगा =पी<उप>मैं / एन.
उदाहरण
#include <iostream>
#include <cmath>
using namespace std;
long getMaxGCD(long n, long p) {
int count = 0;
long gcd = 1;
while (p % 2 == 0) {
p >>= 1;
count++; //number of times P divided by 2
}
if (count > 0) //if p has some 2s, then
gcd = gcd* (long)pow(2, count / n);
for (long i = 3; i <= sqrt(p); i += 2) { //check for all numbers after 2
count = 0;
while (p % i == 0) {
count++;
p = p / i;
}
if (count > 0) {
gcd = gcd* (long)pow(i, count / n);
}
}
// If n in the end is a prime number
if (p > 2)
gcd = gcd* (long)pow(p, 1 / n);
return gcd;
}
int main() {
long n = 3;
long p = 24;
cout << "MAX GCD: " << getMaxGCD(n, p);
} आउटपुट
MAX GCD: 2
