[BOJ] 1934 - 최대공약수와 최소공배수: 유클리드 호제법

백준 1934번을 푸는데 메모리 초과가 자꾸 떴다.
결국엔 구글링...

최대공약수와 최소공배수를 구하기 위해서는 유클리드 호제법을 일반적으로 사용한다고 한다.
유클리드 호제법에 대한 내용은 제쳐주고 알맹이만 정리하자.

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
    
		BufferedReader br = new BufferedReader(new 
		StringTokenizer st = new StringTokenizer(br.readLine());
        
        // a와 b의 최대공약수와 최소공배수를 출력해보자
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		int d = gcd(a, b);

		System.out.println(d); // 최대공약수
		System.out.println(a * b / d); // 최소공배수
		
	}

	// 최대공약수
	public static int gcd(int a, int b) {

		while (b != 0) {
			int r = a % b; // 나머지를 구해준다.

			// GCD(a, b) = GCD(b, r)이므로 변환한다.
			a = b;
			b = r;
		}
		return a;
	}

}