हमने 'स्टार्ट', 'एंड' और 'नंबर' के रूप में तीन इनपुट वेरिएबल दिए। लक्ष्य प्रारंभ और अंत के बीच संख्याओं के ऐसे जोड़े खोजना है जिनका GCD मान 'संख्या' के बराबर है। उदाहरण के लिए GCD(A,B)=number और A, B दोनों रेंज [स्टार्ट, एंड] में हैं।
आइए उदाहरणों से समझते हैं।
इनपुट - प्रारंभ=5 अंत=20 संख्या=8
आउटपुट − दी गई संख्या के बराबर GCD वाली प्राकृत संख्याओं के युग्मों की संख्या है − 3
स्पष्टीकरण - 5 से 20 के बीच ऐसे जोड़े हैं कि जीसीडी 8 है - (8,8), (8,16), (16,8)
इनपुट - प्रारंभ=5 अंत=20 संख्या=7
आउटपुट − दी गई संख्या के बराबर GCD वाली प्राकृत संख्याओं के युग्मों की संख्या − 2
. हैस्पष्टीकरण − 20 से 30 के बीच ऐसे युग्म हैं कि GCD 7 है - (21,28), (28,21)
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
हम दो दृष्टिकोणों का उपयोग करेंगे। पहला भोले दृष्टिकोण जिसमें हम i=start से i<=end तक लूप के लिए और j=start से j<=end तक आंतरिक लूप का उपयोग करके पार करेंगे। प्रत्येक जोड़ी (i, j) के लिए जाँच करें कि क्या GCD(i,j)==number है। अगर सही वेतन वृद्धि गिनती है।
-
चर प्रारंभ, अंत और संख्या को पूर्णांक के रूप में लें।
-
फ़ंक्शन GCD(int a, int b) पुनरावर्ती है और तर्कों का GCD लौटाता है a,b इसे पास किया गया।
-
यदि b गैर-शून्य है तो यह स्वयं को पुनरावर्ती रूप से GCD(b,a%b) कहता है अन्यथा यह a देता है।
-
फ़ंक्शन GCD_pairs(int start, int end, int number) सीमा चर प्रारंभ, अंत और चर संख्या लेता है और प्रारंभ और अंत के बीच युग्म लौटाता है जिसमें gcd=number होता है।
-
प्रारंभिक गणना 0 के रूप में लें।
-
जोड़ी के प्रत्येक सदस्य के लिए दो लूप का उपयोग करना। बाहरी लूप i=स्टार्ट से i<=end तक और आंतरिक लूप j=स्टार्ट से j<=end तक।
-
युग्म (i,j), GCD(i,j)==number के लिए जाँच करें। अगर सही है, तो इंक्रीमेंट काउंट.
-
अंत में हमें gcd=number के साथ युग्मों की कुल संख्या मिल जाएगी।
-
परिणाम के रूप में वापसी की गिनती।
कुशल दृष्टिकोण
इस दृष्टिकोण में, हम प्रारंभ और अंत के मूल्यों को अद्यतन करेंगे। जोड़ी(i,j) के लिए gcd=number होने के लिए, i,j दोनों को 'संख्या' से विभाज्य होना चाहिए। कम से कम (एंड-स्टार्ट)/नंबर नंबर होंगे जो 'नंबर' को पूरी तरह से विभाजित करेंगे। प्रारंभ और अंत के बीच की संख्याएँ प्राप्त करने के लिए जो 'संख्या' से विभाज्य हैं, हम प्रारंभ =(प्रारंभ + संख्या - 1) / संख्या से अंत =अंत / संख्या; तो ऐसी प्रत्येक संख्या के लिए यदि gcd(i,j)==1 तो ऐसी जोड़ी (i,j) के लिए वृद्धि गणना।
-
चर प्रारंभ, अंत और संख्या को पूर्णांक के रूप में लें।
-
अद्यतन प्रारंभ =(प्रारंभ + संख्या -1)/नंबर। और अंत=अंत/संख्या।
-
फ़ंक्शन GCD(int a, int b) पुनरावर्ती है और तर्कों का GCD लौटाता है a,b इसे पास किया गया।
-
यदि b गैर-शून्य है तो यह स्वयं को पुनरावर्ती रूप से GCD(b,a%b) कहता है अन्यथा यह a देता है।
-
फ़ंक्शन GCD_pairs(int start, int end, int number) सीमा चर प्रारंभ, अंत और चर संख्या लेता है और प्रारंभ और अंत के बीच युग्म लौटाता है जिसमें gcd=number होता है।
-
प्रारंभिक गणना 0 के रूप में लें।
-
जोड़ी के प्रत्येक सदस्य के लिए दो लूप का उपयोग करना। बाहरी लूप i=स्टार्ट से i<=end तक और आंतरिक लूप j=स्टार्ट से j<=end तक।
-
जाँच करें कि क्या युग्म (i,j), GCD(i,j)==1 के लिए है। अगर सही है, तो इंक्रीमेंट काउंट.
-
अंत में हमें gcd=number के साथ युग्मों की कुल संख्या मिल जाएगी।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण (बेवकूफ दृष्टिकोण)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a; }
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == number){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of pairs of natural numbers with GCD equal to given number are: 7
उदाहरण (कुशल दृष्टिकोण)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a;
}
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == 1){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
start = (start + number - 1) / number;
end = end / number;
cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of pairs of natural numbers with GCD equal to given number are: 7