[수학] 유클리드 호제법(최소공배수와 최대공약수)

우리는 초등학생 때부터 숫자들에 대한 최소공배수와 최대공약수 구하는 법을 배운다. 그런데 이 방법을 코드로 옮겨서 생각해보자니 막상 쉽게 떠오르지가 않았다.

보통 최소공배수는 GCD(Greatest Common Divisor), 최소공배수는 LCM(Least Common Multiple)이라고 한다. 마침 이와 관련된 문제를 풀어서 두 수 a, b에 대한 최소공배수와 최대공약수 구하는 방법인 유클리드 호제법에 대해 정리해보았다.

 

---

정의

 

특징

 

Psuedo Code

두 수 A, B에 대한 최대공약수 GCD를 구했다면 최소공배수 LCM은 쉽게 구할 수 있다.

LCM = ( A * B ) / GCD(A, B)

 

---

구현(JAVA)

package prac;

public class GCD
{
     // 재귀를 이용한 최소공배수 구하기
     public static int recursion_gcd(int a, int b)
     {
         if(b==0)
         {
             System.out.println();
             return a;
         }

         return recursion_gcd(b, a%b);
     }

     //  반복문을 이용한 최소공배수 구하기
     public static int loop_gcd(int a, int b)

 

     {
         int temp = 0;

         while(b!=0)
         {
             System.out.println("a : " + a + ", b : " + b);

             temp = b;
             b = a%b;
             a = temp; 
         }

         System.out.println();
         return a;
     }

     // 메인함수 부분
     public static void main(String[] args)
     {
         int a = 20;
         int b = 12;

         System.out.println("1. GCD by recursion : " + recursion_gcd(a, b));
         System.out.println("2. GCD by loop : " + loop_gcd(a, b));
         System.out.println("3. LCM : " + a*b / loop_gcd(a, b));
     }
}

 

결과