[백준 알고리즘/BOJ] 자바(java) 2609번 최대공약수와 최소공배수

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

 

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

 

 

자연수의 최대 크기가 10,000이기 때문에 빠르게 최대공약수를 구할 수 있는 유클리드 호제법을 사용했다. 유클리드 호제법과 그것을 통해 최소공배수를 구하는 방법은 아래 글 참고. 

[백준 알고리즘/BOJ] java 1934번 최소공배수

 

package baekjoon;
import java.util.Scanner;

public class B_2609 {
	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);
		int a = stdin.nextInt();
		int b = stdin.nextInt();
		stdin.close();
		
		int max = gcd(a, b); // 최대공약수
		int min = a * b / max; // 최소공배수
		
		System.out.println(max);
		System.out.println(min);
	}
	public static int gcd(int x, int y) {
		if(y == 0) return x;
		else return gcd(y, x % y);
	}
}