C++에서 재귀 또는 유클리드 알고리즘을 사용하지 않고 두 숫자의 HCF 찾기

우리가 알고 있듯이 HCF 또는 GCD는 유클리드 알고리즘을 사용하여 쉽게 계산할 수 있습니다. 그러나 여기서 우리는 유클리드 알고리즘이나 재귀 알고리즘을 사용하지 않고 GCD 또는 HCF를 생성하는 방법을 볼 것입니다. 두 숫자가 16과 24로 존재한다고 가정합니다. 이 두 숫자의 GCD는 8입니다.

여기에서 접근 방식은 간단합니다. 이 둘 중 더 큰 수를 더 작은 수로 나눌 수 있으면 HCF이고, 그렇지 않으면 (작은 / 2)에서 1로 시작합니다. 현재 요소가 두 숫자를 모두 나누는 경우 HCF입니다.

예시

#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);
}

출력

HCF: 8