หาตัวหารร่วมมาก (GCD) ของหลายตัวเลขใน Java

GCD ของหลายตัวเลข (Array)

GCD ของชุดตัวเลข = GCD(GCD(a,b), c), d)... ใช้คุณสมบัติ associative ของ GCD

ตัวอย่างโค้ด

public class Demo { 
    // GCD ของ 2 ตัว (Euclidean Algorithm - Recursive)
    static int gcd(int a, int b) { 
        if (a == 0) return b; 
        return gcd(b % a, a); 
    } 
    
    // GCD ของ Array
    static int findGCD(int[] arr, int n) { 
        int result = arr[0]; 
        for (int i = 1; i < n; i++) { 
            result = gcd(arr[i], result); 
            if (result == 1) return 1; // Early exit: GCD=1 ไม่มีตัวหารร่วมมากกว่า 1
        } 
        return result; 
    } 
    
    public static void main(String[] args) { 
        int[] arr = {7, 49, 177, 105, 119, 42}; 
        System.out.println("GCD ของอาร์เรย์: " + findGCD(arr, arr.length)); 
    } 
}

ผลลัพธ์

GCD ของอาร์เรย์: 1

คำอธิบาย

1. gcd(a, b) ใช้ Euclidean Algorithm แบบ Recursive: gcd(a,b) = gcd(b%a, a)
2. findGCD เริ่มจาก element แรก แล้วค่อยๆ หา GCD กับตัวถัดไป
3. Early exit: หาก GCD กลายเป็น 1 → หยุดทันที (เพราะ GCD ไม่สามารถมากกว่า 1 ได้แล้ว)

Trace (arr = [7, 49, 177, 105, 119, 42])

result = 7
gcd(49, 7) = 7
gcd(177, 7) = 1  -> Early exit! return 1

Iterative GCD (หลีกเลี่ยง Stack Overflow)

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

Java 17+ : Math.gcd() Built-in

import java.math.BigInteger; 

// สำหรับ int/long
int result = Math.gcd(a, b); // Java 17+ (แค่ int)
long result = Math.gcd(a, b); // Java 17+ (long)

// สำหรับ BigInteger
BigInteger gcd = a.gcd(b); // BigInteger method

// Array GCD ด้วย Stream (Java 17+)
int arrayGcd = Arrays.stream(arr).reduce(Math::gcd).orElse(0);

LCM (Least Common Multiple) ของ Array

static long lcm(long a, long b) { 
    return a / gcd(a, b) * b; // ป้องกัน overflow ด้วยการหารก่อนคูณ
} 

static long findLCM(int[] arr) { 
    long result = arr[0]; 
    for (int i = 1; i < arr.length; i++) { 
        result = lcm(result, arr[i]); 
    } 
    return result; 
}

การประยุกต์ใช้

• ลดรูปเศษส่วน
• หาตัวคูณร่วมน้อย (LCM)
• Cryptography (RSA, Diffie-Hellman)
• Scheduling problems (หาเวลาที่เหตุการณ์ตรงกัน)
• จัดกลุ่มข้อมูล (Grouping)