[JAVA] 최대공약수, 최소공배수 계산 문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 유클리드 호제법으로 계산하여 출력해 보자.

※유클리드 호제법(互除法)

호제법이란 두 수가 서로 상대 수를 나누어서 원하는 수를 얻는 방법을 말한다.

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

실행 결과 

package jungbo;

import java.util.InputMismatchException;

import java.util.Scanner;

public class P124DivisorDenominator {

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int A=0, B=0;

try{

while(true){

System.out.print("첫 번째 수를 입력하세요 : ");

A = scan.nextInt();

break;

}

}catch(InputMismatchException e){

System.out.println("숫자만 입력해야 합니다.");

}

try{

while(true){

System.out.print("두 번째 수를 입력하세요 : ");

B = scan.nextInt();

break;

}

}catch(InputMismatchException e){

System.out.println("숫자만 입력해야 합니다.");

}

scan.close();

int big, small; //큰수 작은수 넣어줄 변수

int mok, na;  //몫 나머지

int GCM, LCM; //최대공약수, 최소공배수

if(A>=B){

big = A;

small = B;

}else{

big = B;

small = A;

}

while(true){

mok = big/small;

na = big-mok*small;//big%small

if(na == 0){

GCM = small;

LCM = (A*B)/GCM;

System.out.println(A + "와 "+ B +"의 최대공약수 : " + GCM);

System.out.println(A + "와 "+ B +"의 최소공배수 : " + LCM);

break;

}

big = small;

small = na;

}

}

}