[자바]두 수를 입력받아 최대공약수,최소공배수 구하기 프로그램(유클리드 호제법)

유클리드 호제법을 이용하여 최대공약수와 최소공배수를 구하는 프로그램을 작성 하였습니다.

유클리드 호제법 알고리즘은 아래와 같습니다.

1. 두 수를 입력받는다.

2. 두 수중 큰수와 작은수를 구분한다.

3. 두 수를 나눈 나머지가 0일때 까지 큰수와 작은수를 나눈다.

4.나머지가 0이 되는 순간 큰수가 최대공약수이다.

5.처음 입력받은 두수의 곱을 최대공약수로 나누면 최소공배수가된다.

이러한 사항을 바탕으로 자바로 프로그램을 작성하여 보았습니다.

package Itpangpang;
 
import java.util.Scanner;
 
public class GCDLCM {
    public static void main(String[] args) {
        int val1,val2;
        int r=1;
        int LCM;
        
        Scanner sc = new Scanner(System.in);
        
        System.out.print("첫번째 수를 입력하시오 : ");
        val1 = sc.nextInt();
        System.out.print("두번째 수를 입력하시오 : ");
        val2 = sc.nextInt();
        
        int tmp1=val1,tmp2=val2;//최소공배수를 구하기 위해 입력받은 값 저장
        if(val1<val2){//2번째 입력수가 클 경우 큰수를 val1으로 변경
            val1 = tmp2;
            val2 = tmp1;
         }
 
         while(r>0){//유클리드 호제법을 이용한 GCD(최대공약수)구하기
             r = val1 % val2;
             val1 = val2;
             val2 = r;
          }
         LCM = tmp1* tmp2/val1;//LCM(최소공배수)구하기
         System.out.println("GCD(최대공약수) : "+ val1);
         System.out.println("LCM(최소공배수) : "+ LCM);
    }
}
 
 

 

출력결과