เขียนโปรแกรม C# หา GCD และ LCM

GCD (Greatest Common Divisor) - ตัวหารร่วมมาก

GCD คือจำนวนเต็มบวกที่มากที่สุดที่หารลงตัวทั้งสองจำนวน

ตัวอย่าง: GCD(10, 16) = 2

LCM (Least Common Multiple) - ตัวคูณร่วมน้อย

LCM คือจำนวนเต็มบวกที่น้อยที่สุดที่หารลงตัวด้วยทั้งสองจำนวน

ตัวอย่าง: LCM(10, 16) = 80

ความสัมพันธ์ระหว่าง GCD และ LCM

สูตร: LCM(a, b) × GCD(a, b) = a × b

ดังนั้น: LCM = (a × b) / GCD

อัลกอริทึม Euclidean Algorithm (หา GCD)

วิธีที่มีประสิทธิภาพที่สุดสำหรับการหา GCD:

1. หาร a ด้วย b เก็บเศษเป็น r
2. ให้ a = b, b = r
3. ทำซ้ำจนกว่า b = 0
4. GCD = a

โค้ดตัวอย่างสมบูรณ์ (แก้ไขจากต้นฉบับที่มี Bug)

using System;

namespace GCD_LCM {
    class Program {
        static void Main(string[] args) {
            Console.Write("ป้อนตัวเลขแรก: ");
            int val1 = Convert.ToInt32(Console.ReadLine());
            
            Console.Write("ป้อนตัวเลขที่สอง: ");
            int val2 = Convert.ToInt32(Console.ReadLine());
            
            int n1 = val1;
            int n2 = val2;
            int x;
            
            // Euclidean Algorithm
            while (n2 != 0) {
                x = n2;
                n2 = n1 % n2;
                n1 = x;
            }
            
            int gcd = n1;
            int lcm = (val1 * val2) / gcd;  // ใช้สูตรความสัมพันธ์
            
            Console.WriteLine("\n--- ผลลัพธ์ ---");
            Console.WriteLine("GCD ของ {0} และ {1} = {2}", val1, val2, gcd);
            Console.WriteLine("LCM ของ {0} และ {1} = {2}", val1, val2, lcm);
            
            Console.ReadKey();
        }
    }
}

ตัวอย่างผลลัพธ์

ป้อนตัวเลขแรก: 10
ป้อนตัวเลขที่สอง: 16

--- ผลลัพธ์ ---
GCD ของ 10 และ 16 = 2
LCM ของ 10 และ 16 = 80

ฟังก์ชัน Helper แบบ Reusable

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

public static int CalculateLCM(int a, int b) {
    return (a * b) / CalculateGCD(a, b);
}

⚠️ หมายเหตุ

โค้ดต้นฉบับมีข้อบกพร่องที่ Console.WriteLine("LCM: ", val1, val2, resLCM); - ขาด Format Specifier ทำให้ไม่แสดงค่า โค้ดข้างต้นได้แก้ไขแล้ว