Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में N से कम या बराबर तीन पूर्णांक ढूंढना जिनका LCM अधिकतम हो


परिचय

इस ट्यूटोरियल में हम 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

समस्या समाधान के चरण

  1. यदि संख्या विषम (odd) है तो अधिकतम LCM वाली तीन संख्याएं n, n - 1, और n - 2 हैं।
  2. यदि संख्या सम (even) है और n और n - 3 का GCD 1 है तो तीन संख्याएं n, n - 1, और n - 3 हैं।
  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 के बीच सामान्य गुणनखंड से बचना होता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. - C++ में निरपेक्ष अंतर 1 से कम या बराबर होने वाले अधिकतम तत्वों की संख्या ज्ञात करें

    मान लीजिए हमारे पास n तत्वों का एक सरणी है। हमें सरणी से चुनने के लिए तत्वों की अधिकतम संख्या ढूंढनी है, जैसे कि चुने गए किन्हीं दो तत्वों के बीच का निरपेक्ष अंतर 1 से कम या बराबर हो। इसलिए यदि सरणी [2, 2, 3, 4, 5] की तरह है, तो तत्व 3 होगा, इसलिए अधिकतम संख्या वाला अनुक्रम 2, 2, 3 है। 0 और 1 का निर

  1. - C++ में n से कम या बराबर सभी फैक्टोरियल संख्याएं खोजें

    यहां हम देखेंगे कि n से कम या बराबर सभी फैक्टोरियल संख्याओं को कैसे प्रिंट किया जाए। एक संख्या N को फैक्टोरियल संख्या कहा जाता है यदि यह किसी धनात्मक संख्या का फैक्टोरियल है। इसलिए कुछ फैक्टोरियल संख्याएं हैं: 1, 2, 6, 24, 120। फैक्टोरियल संख्याओं को प्रिंट करने के लिए, हमें सीधे फैक्टोरियल खोजने क

  1. - C++ प्रोग्राम: अद्वितीय जोड़े ढूंढें जहां प्रत्येक तत्व N से कम या बराबर हो

    इस लेख में, हम एक प्रोग्राम पर चर्चा करेंगे जो N से कम या बराबर तत्वों वाले संख्याओं के अद्वितीय जोड़े ढूंढता है और कुछ शर्तों का पालन करता है - दो संख्याओं के बीच अंतर का वर्ग उन दो संख्याओं के LCM के बराबर होना चाहिए। उन दो संख्याओं का HCF किन्हीं दो क्रमागत संख्याओं के गुणनफल के रूप में दर्शाया