[2609] 최대공약수와 최소공배수

[Java]

문제 링크: https://www.acmicpc.net/problem/2609

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

 

[문제]

1. 두 개의 자연수를 입력 받습니다.
2. 출력 첫 째줄에는 최대공약수, 둘 째줄에는 최소공배수를 출려하십시오.

 

두 수의 최대공약수를 구한 후, 최대공약수를 이용하여 최소공배수를 구하는 문제입니다.

우선 최대공약수를 설명하기 전에 약수와 공약수를 살펴보도록하겠습니다.

 

---

 

약수

특정수를 나누어 떨어지게(나누었을 때, 나머지가 0이되는)하는 수를 뜻합니다.

ex) 8의 약수는 1,2,4,8이 있습니다.

 

공약수

두개 이상의 수가 있을 때, 각자 가지고 있는 약수가 공통되는 경우 해당 수를 공약수라고 합니다.

ex) 16의 약수는 1,2,4,16이 있으며, 8과 16의 공약수는 1,2,4입니다.

 

최대공약수(GCD: Greatest Common Divisor)

공약수 중 최대값를 의미합니다.

ex) 8과 16의 최대공약수는 4입니다.

 

저희는 유클리드 호제법을 통해 GCD를 구할 것 이며, 방법은 크게 '반복문'을 사용하는 방법, '재귀함수'를 사용하는 방법 두 가지가 있습니다.

 

1. 반복문

while(b!=0){
	int temp = b;
	b = a%b;
	a = temp;
}

 

2. 재귀 함수

public static int gcd(int a, int b) {
    if(b == 0)
        return a;
    else
        return gcd(b,a%b);
}

 

최소공배수

두 개 이상의 수의 공통된 배수 중 가장 같은 수를 뜻합니다. GCD를 이용한 최소공배수를 구하는 방법으로는 임의의 자연수 a와 b가 입력되었다고 할 때 아래와 같습니다.

a*b/gcd(a,b)

---

[코드]

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

public class Main {
	
	public static int gcd(int a, int b) {
		if(b == 0)
			return a;
		else
			return gcd(b,a%b);
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		bw.write(String.valueOf(gcd(a,b))+'\n');
		bw.write(String.valueOf(a*b/gcd(a,b)));
		br.close();
		bw.close();
	}
}

 

최소공약수와 최소공배수에 대한 지식이 없으신 경우 풀기 어려우며, 이렇게 특정 지식이 필요한 문제의 경우에는 관련 지식을 습득한 후에 구현해보는 것을 추천드립니다.