BOJ 2609 - 최대공약수와 최소공배수

입력

• 두 개의 자연수 (10,000 이하의 자연수)

출력

• 첫 줄에는 두 수의 최대공약수
• 둘째 줄에는 두 수의 최소공배수

풀이방법

• 유클리드 호제법 이용하여 최대공약수 구하기
  • GCD(x,y) = GCD(y,r)
  • r=x%y
  • r=0일 때의 y가 최대공약수
• 최소공배수는 (두 수의 곱)/(최대공약수)

코드

import java.io.*;
import java.util.*;

public class BOJ_2609 {
	public static int GCD(int x, int y) {
		while(y!=0) {
			int r=x%y;
			
			x=y;
			y=r;
		}
		
		return x;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		int a=Integer.parseInt(st.nextToken());
		int b=Integer.parseInt(st.nextToken());
		
		int x=a;
		int y=b;
		int gcd=GCD(x,y);
		
		System.out.println(gcd);
		System.out.println(x*y/gcd);
	}
}