इस सेक्शन में हम देखेंगे कि दिए गए GCD और LCM मानों का उपयोग करके नंबर पेयर्स की संख्या कैसे प्राप्त करें। मान लीजिए GCD और LCM मान 2 और 12 हैं। अब नंबरों के संभावित पेयर्स हैं (2, 12), (4, 6), (6, 4) और (12, 2)। इसलिए हमारा प्रोग्राम पेयर्स की संख्या ढूंढेगा। वह 4 है।
आइए एल्गोरिदम देखें कि इस समस्या को हल करने की तकनीक क्या होगी।
एल्गोरिदम
countPairs(gcd, lcm): Begin if lcm, gcd से विभाज्य नहीं है, तो return 0 temp := lcm/gcd c := primeFactorCount(temp) res := 1 को c बार लेफ्ट शिफ्ट करें return res End primeFactorCount(n): Begin count := 0 जब तक n ऑड नहीं है, count बढ़ाएं और n को 2 से विभाजित करें i := 3 से, जब i² < n, i को 2 से बढ़ाकर, करें यदि n, i से विभाज्य है, तो count बढ़ाएं जब तक n, i से विभाज्य है, करें n := n / i done end if done if n > 2, then count को 1 से बढ़ाएं return count End
उदाहरण
#include<iostream> #include<cmath> using namespace std; int primeFactorCount(int); int countPairs(int gcd, int lcm) { if(lcm % gcd != 0) return 0; int temp = lcm/gcd; return (1 << primeFactorCount(temp)); } int primeFactorCount(int n){ int count = 0; if(n%2 == 0){ //यदि n 0 से विभाज्य है, तो अगले भाग में प्रवेश करें count++; while(n%2 == 0) n = n/2; } //अब n ऑड है, इसलिए यदि हम n को 2 से बढ़ाएं, तो सभी नंबर ऑड होंगे for(int i = 3; i*i <= n; i = i + 2){ if(n%i == 0){ //यदि n 0 से विभाज्य है, तो अगले भाग में प्रवेश करें count++; while(n%i == 0) n = n/i; } } if(n > 2) count++; return count; } int main() { cout << "Possible pairs of GCD = 2, and LCM = 12 is " <<countPairs(2, 12); }आउटपुट
Possible pairs of GCD = 2, and LCM = 12 is 4