โปรแกรม Java หาตัวหารร่วมมาก (GCD) ของ 2 ตัวเลข

ในบทความนี้ เราจะเรียนรู้วิธีหาตัวหารร่วมมาก (GCD - Greatest Common Divisor) ของ 2 ตัวเลขในภาษา Java GCD คือจำนวนที่มากที่สุดที่หารทั้งสองตัวเลขลงตัว

ตัวอย่างการทำงาน

อินพุต:

Value_1: 18, Value_2: 24

เอาต์พุต:

GCD of the two numbers: 6

อัลกอริทึม (แบบตรวจสอบทุกตัว)

1. เริ่มต้นโปรแกรม
2. ประกาศตัวแปร: input_1, input_2, gcd
3. รับค่าจากผู้ใช้ หรือกำหนดค่าไว้ล่วงหน้า
4. วนลูป for จาก 1 ถึง min(input_1, input_2) ตรวจสอบหารลงตัวทั้งคู่
5. เก็บค่าที่หารลงตัวได้ล่าสุด (จะเป็นค่ามากที่สุด)
6. แสดงผลลัพธ์
7. จบโปรแกรม

ตัวอย่างที่ 1: รับค่าจากผู้ใช้ (แบบตรวจสอบทุกตัว)

import java.util.Scanner;

public class GCD {
    public static void main(String[] args) {
        int input_1, input_2, gcd = 1;

        Scanner reader = new Scanner(System.in);
        System.out.println("A reader object has been defined");
        System.out.print("Enter a first number: ");
        input_1 = reader.nextInt();
        System.out.print("Enter a second number: ");
        input_2 = reader.nextInt();

        for (int i = 1; i <= input_1 && i <= input_2; i++) {
            if (input_1 % i == 0 && input_2 % i == 0) {
                gcd = i;
            }
        }

        System.out.printf("\nThe GCD of %d and %d is: %d", input_1, input_2, gcd);
    }
}

ตัวอย่างที่ 2: กำหนดค่าไว้ล่วงหน้า

public class GCD {
    public static void main(String[] args) {
        int input_1 = 12, input_2 = 18, gcd = 1;

        System.out.print("The first number is " + input_1);
        System.out.print("\nThe second number is " + input_2);

        for (int i = 1; i <= input_1 && i <= input_2; i++) {
            if (input_1 % i == 0 && input_2 % i == 0) {
                gcd = i;
            }
        }

        System.out.printf("\nThe GCD of %d and %d is: %d", input_1, input_2, gcd);
    }
}

วิธีที่ดีกว่า: Euclidean Algorithm (O(log n))

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

// ใช้งาน
int result = gcd(24, 18); // ได้ 6

Euclidean Algorithm เร็วกว่ามากสำหรับตัวเลขใหญ่ และเป็นมาตรฐานในการคำนวณ GCD