Thuật toán tìm USCLN và BSCNN

Note: Đây là cách hiểu của mình, ko phải phát biểu thuật toán. Thuật toán được trình bày ở dạng ngôn ngữ tự nhiên và có code demo, còn tính đúng đắn đã được Euclid chứng minh, khỏi bàn cãi.
Thuật toán tìm ƯỚC SỐ CHUNG LỚN NHẤT của 2 số a và b:
Cách 1 (trừ dần):
Bước 1: so sánh a và b

• Nếu a > b: thì lấy a – b rồi gán cho a. Quay về bước 1
• Nếu a < b: thì lấy b – a rồi gán cho b. Quay về bước 1
• Nếu a = b: nhảy sang bước 2.

Bước 2: USCLN là a hoặc b.
Code demo:

while (a != b)
{
     if (a > b)
          a = a - b;
     else
          b = b - a;
}
return a;

Lưu ý: khi code, cần gán a và b vào 2 biến tạm (ví dụ a’ và b’) để khỏi làm thay đổi giá trị của a và b.

Cách 2 (chia lấy dư – tối ưu hơn):
Bước 1: so sánh a và b

• Nếu a>b: thì lấy a % b rồi gán cho a. Quay về bước 1
• Nếu a<b: thì lấy b % a rồi gán cho b. Quay về bước 1
• Nếu a=0 hoặc b=0: nhảy sang bước 2.

Bước 2:
Nếu a = 0 USCLN là b.
Nếu b = 0 USCLN là a.
Code demo:

while (a !=0 && b!=0)
{
     if (a > b)
          a = a % b;
     else
          b = b % a;
}
if (a == 0) return b;
else return a;

Thuật toán tìm BỘI SỐ CHUNG NHỎ NHẤT của 2 số a và b:
Quá đơn giản,^^: chỉ cần lấy a x b / USCLN( a, b) là xong.
Code demo:

BSCNN = a * b / USCLN (a, b);