[백준 2609번] 최대공약수와 최소공배수 - JAVA 알고리즘

 

2609번

문제
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
예제 입력	예제 출력
24 18	6 72

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 선언
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 선언

		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//==========1.숫자를 입력한다.=========
		int num1 =Integer.parseInt(st.nextToken());
		int num2 =Integer.parseInt(st.nextToken());

		
		//==========3. 분자와 분모의 최대공약수를 구한다.==========
		long big = 0;	//큰수
		long small = 0; //작은수
		
		if(num1>num2) {//큰수 구하기
			big = num1;	
			small = num2;
		}else {
			big = num2;	
			small = num1;
		}
		
		int quotient , remainder , greatest, least; //목,나머지,최대공약수, 최소공배수
		//최대공약수 구하기
		while (true) {
			quotient  = (int) (big / small);
			remainder  = (int) (big - quotient  * small);
			if (remainder  == 0) {
				greatest = (int) small;
				least = num1 * num2 / greatest;
				break;
			} else {
				big = small;
				small = remainder ;
			}
		}
		
		bw.write(greatest+"\n"+least);
		
		bw.close();
		br.close();
	}
}

실행 결과

개인적으로 정리한 내용을 간단하게 풀어 작성했습니다. 이해가 안가는 부분은 댓글 남겨주시면 설명해드리겠습니다.