ตัวหารร่วม (Common Divisors) ของสองจำนวนใน Java

Common Divisors (ตัวหารร่วม)

หาจำนวนตัวหารร่วมของสองจำนวน = หาตัวหารของ GCD ของสองจำนวนนั้น

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

public class Demo { 
    // GCD แบบ Recursive
    static int gcd(int a, int b) { 
        if (a == 0) return b; 
        return gcd(b % a, a); 
    } 
    
    // นับจำนวนตัวหารร่วม
    static int countCommonDivisors(int a, int b) { 
        int g = gcd(a, b); 
        int count = 0; 
        
        // ตรวจสอบตัวหารจนถึง sqrt(g)
        for (int i = 1; i <= Math.sqrt(g); i++) { 
            if (g % i == 0) { 
                if (g / i == i) 
                    count += 1; // ตัวหารซ้ำ (perfect square)
                else 
                    count += 2; // คู่ตัวหาร (i, g/i)
            } 
        } 
        return count; 
    } 
    
    public static void main(String[] args) { 
        int a = 68, b = 34; 
        System.out.println("ตัวหารร่วมของ " + a + " และ " + b + ": " + countCommonDivisors(a, b)); 
    } 
}

ผลลัพธ์

ตัวหารร่วมของ 68 และ 34: 4

คำอธิบาย

1. หา GCD(68, 34) = 34
2. หาตัวหารของ 34: 1, 2, 17, 34 → 4 ตัว

Trace

gcd(68, 34):
  gcd(34, 68%34=0) -> gcd(34, 0) -> 34

Divisors of 34:
i=1: 34%1=0, 34/1=34 != 1 -> count+=2 (1, 34)
i=2: 34%2=0, 34/2=17 != 2 -> count+=2 (2, 17)
i=3: 34%3≠0
i=4: 34%4≠0
i=5: 5 > sqrt(34)≈5.8, loop ends
Total: 4

การหาตัวหารร่วมทั้งหมด (List them)

static List getCommonDivisors(int a, int b) { 
    int g = gcd(a, b); 
    List divisors = new ArrayList<>(); 
    
    for (int i = 1; i * i <= g; i++) { 
        if (g % i == 0) { 
            divisors.add(i); 
            if (i != g / i) 
                divisors.add(g / i); 
        } 
    } 
    Collections.sort(divisors); 
    return divisors; 
}
// 68, 34 -> [1, 2, 17, 34]

ความซับซ้อน

Java 17+ Stream Version

static long countCommonDivisorsModern(int a, int b) { 
    int g = java.lang.Math.gcd(a, b); 
    return java.util.stream.LongStream.rangeClosed(1, (long)Math.sqrt(g)) 
        .filter(i -> g % i == 0) 
        .map(i -> i * i == g ? 1 : 2) 
        .sum(); 
}