Chương trình C triển khai thuật toán Euclid tìm UCLN và BCNN

Đề bài

Triển khai thuật toán Euclid để tìm ước chung lớn nhất (UCLN/GCD) và bội chung nhỏ nhất (BCNN/LCM) của hai số nguyên.

Giải pháp

Đệ quy Euclid:

int gcd_rec(int x, int y) {
    if (y == 0) return x;
    return gcd_rec(y, x % y);
}

BCNN = (a * b) / UCLN

Chương trình hoàn chỉnh

#include <stdio.h>

int gcd_rec(int, int);

void main() {
    int firstno, secondno, gcd;
    printf("Nhập hai số để tìm UCLN và BCNN: ");
    scanf("%d%d", &firstno, &secondno);
    if (firstno * secondno != 0) {
        gcd = gcd_rec(firstno, secondno);
        printf("\nUCLN của %d và %d là %d\n", firstno, secondno, gcd);
        printf("\nBCNN của %d và %d là %d\n", firstno, secondno, (firstno * secondno) / gcd);
    } else {
        printf("Một trong hai số là 0: Thoát\n");
    }
}

int gcd_rec(int x, int y) {
    if (y == 0) return x;
    return gcd_rec(y, x % y);
}

Kết quả

Nhập hai số để tìm UCLN và BCNN: 4 8
UCLN của 4 và 8 là 4
BCNN của 4 và 8 là 8