Tìm ƯCLN (GCD) 2 số dùng while loop trong C

Đề bài

Tìm ước chung lớn nhất (GCD) của 2 số bất kỳ bằng C.

Giải pháp

Người dùng nhập 2 số, tìm GCD - số lớn nhất chia hết cả 2 số không dư.

Logic tìm GCD (Thuật toán Euclid)

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

Chương trình 1: Dùng while loop (Euclid)

#include <stdio.h>

int main() {
    int a, b, rem;
    printf("Nhập 2 số: ");
    scanf("%d %d", &a, &b);
    
    while (b != 0) {
        rem = a % b;
        a = b;
        b = rem;
    }
    printf("ƯCLN (GCD) = %d\n", a);
    return 0;
}

Kết quả chương trình 1

Nhập 2 số: 8 12
ƯCLN = 4
Kiểm tra: 8=2×2×2, 12=2×2×3 → ƯCLN=2×2=4

Chương trình 2: Dùng for loop

#include <stdio.h>

int main() {
    int num1, num2, i, GCD;
    printf("Nhập 2 số: ");
    scanf("%d %d", &num1, &num2);
    
    for(i = 1; i <= num1 && i <= num2; ++i) {
        if (num1 % i == 0 && num2 % i == 0)
            GCD = i;
    }
    printf("ƯCLN = %d\n", GCD);
    return 0;
}

Kết quả chương trình 2

Nhập 2 số: 24 48
ƯCLN = 24