[JAVA] 백준 2609번 : 최대공약수와 최소공배수

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

 

문제

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

입력

첫째 줄에는 두 개의 자연수 (10,000이하)

출력

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

풀이

최대공약수 문제를 풀기 위해선 유클리드 호제법 이라는 알고리즘을 이용하면 쉽다!
유클리드 호제법이란 2개의 자연수(또는 정식)의 최대공약수를 구하는 알고리즘의 하나로,
호제법이라는 말이 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

이론은 간단하다.
2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (이때, a>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지를 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

예시를 들어 보면 좀 더 이해하기 쉽다.
24와 18의 최대공약수를 구한다면

24 = 18x1 + 6
18 = 6x3 + 0 -> 나머지가 0이 되었음

나머지가 0이 될 때 나누는 수인 6이 24와 18의 최대공약수이다.


최대공약수를 구하는 코드는 아래와같다.

int gcd(int a, int b){
	while(b!=0){
    		int r=a%b;
            a=b;
            b=r;
    }
	return a;
}
            

최소공배수는 최대공약수를 이용해주면 쉽게 구할 수 있는데, a와 b를 곱한 수에 최대공약수를 나눠주면 된다.
(a와 b의 최소공배수) = (axb)/(a와 b의 최대공약수)

public class bj2609 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		
		int a= s.nextInt();
		int b= s.nextInt();
	
		System.out.println(gcd(a,b)); // 최대공약수 출력
		System.out.println(a*b/gcd(a,b)); // 최소공배수 출력
		
		s.close();
		
	}
	// 최대 공약수 구하는 함수
	public static int gcd(int a, int b) {
		while(b!=0) {
			int r = a%b;
			a=b;
			b=r;
		}
		return a;
	}

}