रेंज [L, R] में सभी संभावित सह-अभाज्य विशिष्ट तत्व युग्म

यहां हम देखेंगे कि रेंज से सह-अभाज्य युग्मों की संख्या कैसे गिनें, जहां एक संख्या एक से अधिक युग्म में नहीं आएगी।

तर्क पर चर्चा करने से पहले, आइए देखें कि सह-अभाज्य संख्याएं क्या हैं? सह-अभाज्य संख्याएं वे संख्याएं हैं जिनका केवल एक धनात्मक पूर्णांक भाजक होता है, वह है 1। दूसरे शब्दों में, हम कह सकते हैं कि इन दो संख्याओं का GCD 1 है।

यहां हम निचली और ऊपरी सीमा प्रदान कर रहे हैं। यदि निचली और ऊपरी सीमाएं 1 और 6 हैं, तो तीन युग्म हैं। ये हैं (1, 2), (3, 4) और (5, 6)।

इस समस्या को हल करने का दृष्टिकोण है: यदि संख्याएं क्रमागत हैं, तो वे हमेशा सह-अभाज्य होती हैं। तो गिनती (R - L + 1)/2 होगी। यदि (R - L + 1) विषम है तो एक संख्या बच जाएगी, जिसे किसी युग्म में नहीं रखा जाएगा, यदि यह सम है तो सभी युग्म बनाएंगे।

एल्गोरिदम

countCoPrimePairs(L, R)

शुरुआत
    return (R - L + 1) / 2
समाप्त

उदाहरण

#include <iostream>
using namespace std;

int countCoPrimePairs(int L, int R) {
    return (R - L + 1) / 2;
}

int main() {
    int l = 1, r = 6;
    cout << "Number of co-prime pairs: " << countCoPrimePairs(l, r);
    return 0;
}

आउटपुट

Number of co-prime pairs: 3