[브론즈 1] 2609. 최대공약수와 최소공배수 (Java)

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

금주는 수학 문제 관련된 알고리즘을 주로 풀이를 진행할 예정입니다!

---

※  문제를 요약하면 아래와 같습니다.

▶ 두 수가 입력 되면 최대공약수와 최소공배수를 출력합니다.

◈ Input

24 18

◈ Output

6
72

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 최대 공약수는 유클리드 호제법 구현. ( 저는 아래 위키에서 예시만 보고 직접 코드로 구현 해보았습니다! )

 ( Ref : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 )

▶ 최소공배수 = 두 수의 곱 / 최대공약수 형태로 구현.

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

public class Main {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bReader.readLine());
		
		int nFirstNum = Integer.parseInt(st.nextToken());
		int nSecondNum = Integer.parseInt(st.nextToken());
		
		int nMul = nFirstNum * nSecondNum;
		
		// 최대 공약수는 나머지가 0이 될 때 까지.
		int nRemainder = 0;
		while(nSecondNum > 0) {
			nRemainder = nFirstNum % nSecondNum;
			nFirstNum = nSecondNum;
			nSecondNum = nRemainder;
		}
		
		// 최대 공약수
		// GCL is stands for Greatest Common divisor
		int nGCL = nFirstNum;
		
		
		// 최소 공배수
		// 최소 공배수 = 두 수의 곱 / 최대 공약수.
		// LCM is stands for Least Common Multiple
		int nLCM = nMul / nGCL;
		
		
		System.out.println(nGCL);
		System.out.println(nLCM);
	}
}

읽어주셔서 감사합니다!

Good Luck! (피드백 고맙습니다)