दो संख्याओं के सामान्य भाजक वे संख्याएं हैं जो उन दोनों के भाजक हैं।
उदाहरण के लिए, 12 के भाजक 1, 2, 3, 4, 6, 12 हैं। 18 के भाजक 1, 2, 3, 6, 9, 18 हैं। इस प्रकार, 12 और 18 के सामान्य भाजक 1, 2, 3, 6 हैं। इनमें सबसे बड़ा, शायद आश्चर्यजनक रूप से, 12 और 18 का महत्तम समापवर्तक (GCD) कहलाता है। दो पूर्णांकों a और b के महत्तम समापवर्तक के लिए सामान्य गणितीय संकेतन (a, b) द्वारा दर्शाया जाता है। इसलिए, (12, 18) = 6।
महत्तम समापवर्तक कई कारणों से महत्वपूर्ण है। उदाहरण के लिए, इसका उपयोग दो संख्याओं का लघुत्तम समापवर्त्य (LCM) निकालने के लिए किया जा सकता है, यानी वह सबसे छोटी धनात्मक पूर्णांक जो इन संख्याओं का गुणक हो। संख्याओं a और b का लघुत्तम समापवर्त्य a*b*(a, b) के रूप में गणना की जा सकती है।
उदाहरण के लिए, 12 और 18 का लघुत्तम समापवर्त्य 12*18*(12, 18)=12*18*6 है।
Input: 4, 10, 16, 14 Output: 2
व्याख्या
दो या अधिक पूर्णांकों का GCD वह सबसे बड़ा पूर्णांक है जो दोनों संख्याओं को सटीक रूप से विभाजित कर सके (बिना शेष के)।
उदाहरण
#include <iostream>
using namespace std;
int gcd(int a,int b) {
int temp;
while(b > 0) {
temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
int a[] = {4, 10, 16, 14};
int n = 4;
int r = a[0];
for(int i=1; i<n; i++) {
r = gcd(r, a[i]);
}
cout << r << endl;
return 0;
}
आउटपुट
2
