C++-এ দিয়ে गये GCD এবং LCM থেকে যেকোনো পেয়ার খুঁজে বের করা

এই সেকশনে আমরা দেখব কীভাবে দিয়ে गये GCD এবং LCM মান ব্যবহার করে সংখ্যা পেয়ার এর সংখ্যা বের করা যায়। মনে করুন GCD এবং LCM মান গুলো ২ এবং ১২। এখন সংখ্যা পেয়ার গুলোর সম্ভাবনা হল (2, 12), (4, 6), (6, 4) এবং (12, 2)। তাই আমাদের প্রোগ্রাম পেয়ার গুলোর সংখ্যা বের করবে। সেটি হল ৪।

আসুন অ্যালগরिदমটি দেখি কী পদ্ধতি ব্যবহার করা হয়েছে এই সমস্যা সমাধানের জন্য।

অ্যালগরিদম

countPairs(gcd, lcm): 
শুরু 
    যদি lcm gcd দিয়ে বিভাজ্য না হয়, তবে
        0 রিটার্ন করো
    temp := lcm/gcd
    c := primeFactorCount(temp)
    res := 1 কে বামে c বার শিফ্ট করো
    res রিটার্ন করো
শেষ

primeFactorCount(n): 
শুরু 
    count := 0
    n অড না হওয়া পর্যন্ত, count বাড়াও এবং n কে ২ দিয়ে ভাগ করো
    i := 3 থেকে, i² <= n থাকলে, i কে ২ বাড়িয়ে, করো
        যদি n i দিয়ে বিভাজ্য হয়, তবে
            count বাড়াও
            যতক্ষণ n i দিয়ে বিভাজ্য হয়, করো
                n := n / i
            শেষ
        শেষ যদি
    শেষ
    যদি n > 2, তবে
        count ১ বাড়াও
    count রিটার্ন করো
শেষ

উদাহরণ (C++ কোড)

#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 ২ দিয়ে বিভাজ্য হয়
        count++;
        while(n % 2 == 0)
            n = n/2;
    }
    // এখন n অড, তাই যদি ২ বাড়িয়ে যাই, সব সংখ্যা অড হবে
    for(int i = 3; i*i <= n; i = i + 2) {
        if(n % i == 0) { // যদি n i দিয়ে বিভাজ্য হয়
            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