Tìm HCF của hai số mà không sử dụng thuật toán đệ quy hoặc Euclidean trong C ++

Như chúng ta đã biết, HCF hoặc GCD có thể được tính toán dễ dàng bằng cách sử dụng Thuật toán Euclide. Nhưng ở đây chúng ta sẽ xem cách tạo GCD hoặc HCF mà không cần sử dụng Thuật toán Euclide, hoặc bất kỳ thuật toán đệ quy nào. Giả sử có hai số là 16 và 24. GCD của hai số này là 8.

Đây là cách tiếp cận đơn giản. Nếu số lớn hơn trong hai số này chia hết cho số nhỏ hơn thì đó là HCF, nếu không bắt đầu từ (nhỏ hơn / 2) đến 1, nếu phần tử hiện tại chia cả hai số thì đó là HCF.

Ví dụ

#include <iostream>
using namespace std;
int gcd(int a, int b) {
   int min_num = min(a, b);
   if (a % min_num == 0 && b % min_num == 0)
   return min_num;
   for (int i = min_num / 2; i >= 2; i--) {
      if (a % i == 0 && b % i == 0)
      return i;
   }
   return 1;
}
int main() {
   int a = 16, b = 24;
   cout << "HCF: "<< gcd(a, b);
}

Đầu ra

HCF: 8