백준알고리즘_2609

 

유클리드 호재법

2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘
호재법이라는 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

 

자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면 a,b의 최대공약수와 b,r의 최대공약수는 같다.

이 성질에 따라 a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r'을 구한다.  

나머지가 0이 될때 나눈 수가 a,b의 최대공약수가 된다. 

이 때 a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.

GCD(a, b) = GCD(b, r)

 

유클리드 호제법 사용

// a를 b로 나눈 나머지가 0보다 클 때 까지 반복
static int gcd(int a, int b){ // 최대 공약수
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

 

재귀함수 사용

static int GCD(int a, int b){ // 최대 공약수
	if (a%b == 0) {
		return b;
	}
	return GCD(b, a % b);
}

48, 64의 최대공약수

60 % 48 = 12
48 % 12 = 0
=> 최대 공약수는 12

☞ 최소공배수 : (60 X 48) / 12 = 240

최소 공배수 = (a X b) / (최대공약수)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baek_2609 {
    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()); // String을 int로 변환
        int b = Integer.parseInt(st.nextToken());

        System.out.println(gcd(a, b));
        System.out.println(lcm(a, b));
    }
    
        static int gcd(int a, int b) { // 최대 공약수
            if (a % b == 0) {
                return b; 
            }
            return gcd(b, a % b); //6
        }

    	static int lcm(int a, int b) { // 최소 공배수

            return a * b / gcd(a, b); // (24X18) / 6
        }

}