2609. 최대공약수와 최소공배수 (자바, Java)

이 문제를 통해 유클리드 호제법을 배웠다.

유클리드 호제법이란, a>b인 두 수 a와 b의 최대공약수는 a를 b로 나눈 나머지인 r과 b의 최대공약수이기도 한다는 것이다. 증명은 다음을 참고.

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

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

그렇다면 최소공배수는? 최대공약수를 g라 할 때, A=ag, B=bg (a, b는 서로소) 가 된다.

따라서 최소공배수는 a*b*g가 되고, 이는 (A*B) / g가 된다.

 

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 {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str," ");
		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		
		if (x>y) {
			int temp = x;
			x = y;
			y = temp;
		}
		
		for (int i=x; i>=1; i--) {
			if (x%i==0 && y%i==0) {
				System.out.println(i);
				break;
			}
		}
				
		int k = y;
		
		while (true) {
			
			if (k%y==0 && k%x==0) {
				System.out.println(k);
				break;
			}
			k++;
		}

	}

}