หาตัวหารร่วมมาก (GCD) ของเลข 2 ตัวด้วย while loop ใน C

โจทย์

หา GCD (Greatest Common Divisor) ของเลข 2 ตัว คือตัวเลขมากที่สุดที่หารทั้งคู่ลงตัว

วิธีที่ 1: Euclidean Algorithm (while loop) - เร็วที่สุด

while(b != 0) {
    rem = a % b;
    a = b;
    b = rem;
}
// GCD = a

โปรแกรมตัวอย่าง

#include <stdio.h>
int main() {
    int a, b, rem;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    
    while(b != 0) {
        rem = a % b;
        a = b;
        b = rem;
    }
    printf("GCD = %d\n", a);
    return 0;
}

ผลลัพธ์

enter any two numbers: 8 12
GCD of two numbers is: 4
Check: 8=2*2*2, 12=2*2*3 -> GCD=2*2=4

วิธีที่ 2: ใช้ for loop (Brute Force)

#include <stdio.h>
int main() {
    int n1, n2, i, gcd = 1;
    printf("Enter two numbers: ");
    scanf("%d %d", &n1, &n2);
    
    for(i = 1; i <= n1 && i <= n2; i++) {
        if(n1 % i == 0 && n2 % i == 0) gcd = i;
    }
    printf("GCD = %d\n", gcd);
    return 0;
}

ผลลัพธ์

enter two numbers: 24 48
GCD of two numbers is: 24