জাভা প্রোগ্রাম: রিকার্শন ব্যবহার করে GCD (সর্বোচ্চ সাধারণ ভাজক) বের করা

GCD (Greatest Common Divisor) কী?

দুটি সংখ্যার সর্বোচ্চ সাধারণ ভাজক (GCD) বা HCF হলো সেই সবচেয়ে বড় সংখ্যা যা দুটি সংখ্যাকেও ভাগ করে দেয়। ইউক্লিডিয়ান অ্যালগরিদম (Euclidean Algorithm) এর মাধ্যমে এটি দ্রুত বের করা যায়।

সূত্র: GCD(a, b) = GCD(b, a % b), বেস কেস: GCD(a, 0) = a

ইনপুট ও আউটপুট উদাহরণ

ইনপুট:

Enter two numbers: 24 and 36

আউটপুট:

The G.C.D of 24 and 36 is 12.

অ্যালগরিদম

1. প্রোগ্রাম শুরু করুন
2. তিনটি ইন্টিজার ভেরিয়েবল ঘোষণা করুন: my_input_1, my_input_2, my_result
3. ব্যবহারকারী থেকে দুটি সংখ্যা ইনপুট নিন
4. রিকার্সিভ ফাংশন CommonFactor(a, b) ডিফাইন করুন:
   • বেস কেস: যদি b == 0 হয়, a রিটার্ন করুন
   • রিকার্সিভ কেস: CommonFactor(b, a % b) রিটার্ন করুন
5. ফাংশন কল করুন এবং ফলাফল স্টোর করুন
6. ফলাফল প্রদর্শন করুন
7. প্রোগ্রাম শেষ করুন

উদাহরণ ১: ব্যবহারকারী ইনপুট নেওয়া

import java.util.Scanner;

public class GCD {
    public static void main(String[] args) {
        int my_input_1, my_input_2, my_result;
        System.out.println("Required packages have been imported");
        Scanner my_scanner = new Scanner(System.in);
        System.out.println("A reader object has been defined");
        System.out.print("Enter the first number : ");
        my_input_1 = my_scanner.nextInt();
        System.out.print("Enter the second number : ");
        my_input_2 = my_scanner.nextInt();
        
        my_result = CommonFactor(my_input_1, my_input_2);
        System.out.printf("The G.C.D of %d and %d is %d.", my_input_1, my_input_2, my_result);
    }
    
    public static int CommonFactor(int my_input_1, int my_input_2) {
        if (my_input_2 != 0)
            return CommonFactor(my_input_2, my_input_1 % my_input_2);
        else
            return my_input_1;
    }
}

উদাহরণ ২: পূর্বনির্ধারিত মান ব্যবহার

public class GCD {
    public static void main(String[] args) {
        int my_input_1 = 24, my_input_2 = 36, my_result;
        System.out.println("The numbers are defined as " + my_input_1 + " and " + my_input_2);
        my_result = CommonFactor(my_input_1, my_input_2);
        System.out.printf("The G.C.D of %d and %d is %d.", my_input_1, my_input_2, my_result);
    }
    
    public static int CommonFactor(int my_input_1, int my_input_2) {
        if (my_input_2 != 0)
            return CommonFactor(my_input_2, my_input_1 % my_input_2);
        else
            return my_input_1;
    }
}

ইউক্লিডিয়ান অ্যালগরিদম ট্রেস (24, 36)

CommonFactor(24, 36)
= CommonFactor(36, 24 % 36) = CommonFactor(36, 24)
= CommonFactor(24, 36 % 24) = CommonFactor(24, 12)
= CommonFactor(12, 24 % 12) = CommonFactor(12, 0)
= 12 (বেস কেস: b == 0, রিটার্ন a = 12)

কোড ব্যাখ্যা

• মডুলাস অপারেটর (%): a % b = a বি ভাগ করার বাকি
• আর্গুমেন্ট সোয়াপ: প্রতিটি কলেই (a, b) → (b, a%b) হয়
• টেল রিকার্শন: রিটার্ন স্টেটমেন্টে শুধু রিকার্সিভ কল থাকে (অপ্টিমাইজেবল)
• সময় জটিলতা: O(log min(a,b)) - খুব দ্রুত

ইটারেটিভ ভার্শন (প্রোডাকশন রেডি)

public static int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Java 8+ এन्ह্যান্সড
public static int gcdMath(int a, int b) {
    return java.math.BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue();
}

বিইনস্টাইন অ্যালগরিদম (Binary GCD / Stein's Algorithm)

শুধু বিট অপারেশন ব্যবহার করে (মডুলাস ছাড়া):

public static int binaryGCD(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    
    // ২-এর ঘাত ফ্যাক্টর বের করুন
    int shift = Integer.numberOfTrailingZeros(a | b);
    a >>= Integer.numberOfTrailingZeros(a);
    
    do {
        b >>= Integer.numberOfTrailingZeros(b);
        if (a > b) { int t = a; a = b; b = t; } // swap
        b = b - a;
    } while (b != 0);
    
    return a << shift;
}

একাধিক সংখ্যার GCD

public static int gcdArray(int[] numbers) {
    int result = numbers[0];
    for (int i = 1; i < numbers.length; i++) {
        result = CommonFactor(result, numbers[i]);
        if (result == 1) return 1; // আর্লি এক্সিট
    }
    return result;
}

LCM (Least Common Multiple) বের করা

LCM(a, b) = |a × b| / GCD(a, b)

public static long lcm(int a, int b) {
    return Math.abs((long) a * b) / gcdIterative(a, b);
}

বাস্তব প্রয়োগ

• ভগ্নাংশ সরলীকরণ (Fraction simplification)
• ক্রিপ্টোগ্রাফি (RSA - কো-প্রাইম চেক)
• মডুলার এরিথম্যেটিক, কংগ্রুয়েন্স
• গিয়ার রেশিও, ইঞ্জিনियरিং
• সিডিউলিং, পিরিয়ডিক টাস্ক

জাভা BigInteger GCD

import java.math.BigInteger;

BigInteger a = new BigInteger("12345678901234567890");
BigInteger b = new BigInteger("98765432109876543210");
BigInteger gcd = a.gcd(b);
System.out.println("GCD: " + gcd);