โปรแกรม Java หาตัวคูณร่วมน้อย (LCM) ของ 2 ตัวเลข

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

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

อินพุต:

24 and 18

เอาต์พุต:

The LCM of 24 and 18 is 72

อัลกอริทึม

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

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

import java.util.Scanner;

public class LCM {
    public static void main(String[] args) {
        int input_1, input_2, lcm;

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

        lcm = (input_1 > input_2) ? input_1 : input_2;

        while (true) {
            if (lcm % input_1 == 0 && lcm % input_2 == 0) {
                System.out.printf("The LCM of %d and %d is %d.", input_1, input_2, lcm);
                break;
            }
            ++lcm;
        }
    }
}

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

public class LCM {
    public static void main(String[] args) {
        int input_1 = 24, input_2 = 18, lcm;

        System.out.println("The first number is " + input_1);
        System.out.println("The second number is " + input_2);

        lcm = (input_1 > input_2) ? input_1 : input_2;

        while (true) {
            if (lcm % input_1 == 0 && lcm % input_2 == 0) {
                System.out.printf("\nThe LCM of %d and %d is %d.", input_1, input_2, lcm);
                break;
            }
            ++lcm;
        }
    }
}

วิธีที่มีประสิทธิภาพมากกว่า: ใช้สูตร LCM × GCD = a × b

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

public static int lcm(int a, int b) {
    return (a / gcd(a, b)) * b; // ใช้หารก่อนคูณกันล้น
}

วิธีนี้ใช้ Euclidean Algorithm หา GCD แล้วคำนวณ LCM เร็วกว่ามาก (O(log n))