परिचय
इस ट्यूटोरियल में हम LCM की अवधारणाओं पर आधारित एक प्रोग्राम लिखेंगे। शीर्षक के अनुसार, हमें उन तीन संख्याओं को ढूंढना है जो दी गई संख्या से कम या बराबर हैं जिनका LCM अधिकतम हो।
LCM क्या है?
LCM (लीस्ट कॉमन मल्टीपल) एक संख्या का लघुत्तम समापवर्त्य है। इसे लघुत्तम समापवर्तक भी कहा जाता है। दो धनात्मक संख्याओं a और b के लिए, LCM वह सबसे छोटा पूर्णांक है जो a और b दोनों से समान रूप से विभाज्य होता है।
यदि दी गई पूर्णांक संख्याओं का कोई सामान्य गुणनखंड नहीं है, तो LCM दी गई संख्याओं का गुणनफल होता है।
LCM प्रोग्राम
आइए किन्हीं दो धनात्मक संख्याओं का LCM ढूंढने का प्रोग्राम लिखते हैं।
#include <iostream>
using namespace std;
int main() {
int a = 4, b = 5;
int maximum = max(a, b);
while (true) {
if (maximum % a == 0 && maximum % b == 0) {
cout << "LCM: " << maximum << endl;
break;
}
maximum++;
}
return 0;
}
आउटपुट
20
समस्या समाधान के चरण
- यदि संख्या विषम (odd) है तो अधिकतम LCM वाली तीन संख्याएं n, n - 1, और n - 2 हैं।
- यदि संख्या सम (even) है और n और n - 3 का GCD 1 है तो तीन संख्याएं n, n - 1, और n - 3 हैं।
- अन्यथा तीन संख्याएं n - 1, n - 2, और n - 3 हैं।
उदाहरण कोड
#include <bits/stdc++.h>
using namespace std;
void threeNumbersWithMaxLCM(int n) {
if (n % 2 != 0) {
cout << n << " " << (n - 1) << " " << (n - 2);
} else if (__gcd(n, (n - 3)) == 1) {
cout << n << " " << (n - 1) << " " << (n - 3);
} else {
cout << (n - 1) << " " << (n - 2) << " " << (n - 3);
}
cout << endl;
}
int main() {
int n = 18;
threeNumbersWithMaxLCM(n);
return 0;
}
आउटपुट
17 16 15
व्याख्या
n=18 (सम) के लिए: GCD(18, 15) = 3 ≠ 1, इसलिए हम 17, 16, 15 चुनते हैं। इनका LCM = 17×16×15 = 4080 (क्योंकि ये सह-अभाज्य हैं)।
निष्कर्ष
यह गणितीय अंतर्दृष्टि पर आधारित O(1) समाधान है। विषम n के लिए शीर्ष 3 संख्याएं सह-अभाज्य होती हैं। सम n के लिए, हमें n और n-3 के बीच सामान्य गुणनखंड से बचना होता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।