সি প্রোগ্রামিং: ইউক্লিডীয় পদ্ধতিতে GCD ও LCM

Lecture 2 - GCD & LCM নির্ণয়ের লজিক ও সূত্র

গসাগু (GCD) এবং লসাগু (LCM) নির্ণয় করার জন্য ইউক্লিডীয় পদ্ধতি অত্যন্ত জনপ্রিয় এবং দক্ষ। এই পদ্ধতিতে কোনো অতিরিক্ত বড়-ছোট চেক করার প্রয়োজন হয় না।

১. সোর্স কোড (C Program)

#include <stdio.h>

int main() {
    int num1, num2, n1, n2, rem, gcd, lcm;

    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);

    n1 = num1;
    n2 = num2;

    // ইউক্লিডীয় লজিক
    while(n2 != 0) {
        rem = n1 % n2;
        n1 = n2;
        n2 = rem;
    }

    gcd = n1;
    lcm = (num1 * num2) / gcd;

    printf("GCD = %d\n", gcd);
    printf("LCM = %d\n", lcm);

    return 0;
}

২. বড়-ছোট সংখ্যার "অটো-সোয়াপ" রহস্য

                    ইউক্লিডীয় পদ্ধতির সবচেয়ে সুন্দর দিক হলো—এটি নিজে থেকেই বড় সংখ্যাকে ছোট সংখ্যা দিয়ে ভাগ করার জন্য
                    প্রস্তুত করে নেয়।
                

ধরা যাক, ইউজার প্রথম সংখ্যাটি ছোট (১০) এবং দ্বিতীয় সংখ্যাটি বড় (২৫) ইনপুট দিয়েছেন।

ধাপ ১: লুপ শুরু হলো। rem = 10 % 25। এখানে ভাগশেষ থাকে ১০।

ধাপ ২: n1 = n2 অর্থাৎ n1 এখন ২৫।

ধাপ ৩: n2 = rem অর্থাৎ n2 এখন ১০।

দেখুন, মাত্র একটি ধাপেই n1 বড় হয়ে গেল এবং n2 ছোট হয়ে গেল। এরপর লুপটি স্বাভাবিকভাবে কাজ করবে।

৩. গাণিতিক সূত্র

আমরা জানি, দুটি সংখ্যার গুণফল তাদের গসাগু এবং লসাগুর গুণফলের সমান। সেখান থেকেই লসাগু বের করা হয়েছে:

LCM = (num1 × num2) / GCD