C++-এ দুইটির অধিক সংখ্যার GCD (GCD of Array/Multiple Numbers)

এখানে আমরা দেখব কীভাবে আমরা দুইটির অধিক সংখ্যার GCD বের করতে পারি। দুইটি সংখ্যার GCD বের করা সহজ। যখন আমরা দুইটির অধিক সংখ্যার GCD বের করতে চাই, তবে আমাদের GCD-এর অ্যাসোসিয়েটিভিটি রুল ফলো করতে হবে। উদাহরণস্বরূপ, যদি আমরা {w, x, y, z}-এর GCD বের করতে চাই, তবে এটি হবে {gcd(w,x), y, z}, তারপর {gcd(gcd(w,x), y), z}, এবং অবশেষে {gcd(gcd(gcd(w,x), y), z)}। অ্যারে ব্যবহার করে এটি খুব সহজে করা যায়।

অ্যালগরিদম

gcd(a, b)

begin
    if a is 0, then
        return b
    end if
    return gcd(b mod a, a)
end

getArrayGcd(arr, n)

begin
    res := arr[0]
    for i in range 1 to n-1, do
        res := gcd(arr[i], res)
    done
    return res;
end

উদাহরণ

#include<iostream>
using namespace std;
int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b%a, a);
}
int getArrayGcd(int arr[], int n) {
    int res = arr[0];
    for(int i = 1; i < n; i++) {
        res = gcd(arr[i], res);
    }
    return res;
}
main() {
    int arr[] = {4, 8, 16, 24};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "GCD of array elements: " << getArrayGcd(arr, n);
}

আউটপুট

GCD of array elements: 4