유클리드 호제법에 대해 알아보자!!

유클리드 호제법은 최대공약수를 구하는 알고리즘 중 하나입니다.

최대공약수를 구하면 최소공배수도 구할 수 있겠죠?? ㅎㅎ

간단하므로 짧게 정리!!

1. 유클리드 호제법이란?

  - 유클리드 호제법은 2개의 자연수 또는 정수의 최대공약수를 구할 수 있습니다.

  * 호제법 : 두수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘

  

2. 유클리드 호제법 이해

  ▶ 자연수 또는 정수 A, B에 대해 A를 B로 나눈 나머지를 R이라고 하면 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.

      ① A와 B라는 두 정수가 있고, A가 B보다 큰 값이라고 가정합니다. 

          ( A > B )

      ② A를 B로 나눈 나머지가 R이라고 합니다.

          ( A mod B == R )

      ③ R이 0이라면 최대 공약수는 B 입니다.

          ( A mod B == 0 , GCD = B)

      ④ R이 0이 아니라면, 위의 성질을 이용하여 B와 R의 나머지를 구합니다.

          ( B mod R<A mod B> )

      ⑤ ③이 될때 까지 반복합니다.

   

    ex) 

      ① 35와 20의 최대 공약수  

      ② 35 mod 20 에서 R은 15

      ③ 20 mod 15 에서 R은 5

      ④ 15 mod 5 에서 R은 0 이므로 최대 공약수는 5입니다.

.

3. 유클리드 호제법 구현

  - 최소 공배수는 두 수의 곱에 최대 공약수를 나눈 것이다.

 #include<iostream>
 
 using namespace std;
 
 int gcd(int a, int b) {
     if(a%b==0) {
         return b;
     }
     return gcd(b%a, a);
 }
 
 int main(void) {
     printf("최대 공약수 : %d\n", gcd(35, 20));
     printf("최소 공배수 : %d", 35*20/gcd(35,20));
     
 }

▶ 결과화면