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

 

 

1. 유클리드 호제법 설명

 

 

1) 최대공약수 : GCD

 

 

a, b : 정수

r = a mod b     (즉, a에 b를 나눈 나머지)

이때  0 ≤ r < b 이며, b ≤ a 이다.

 

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

 

즉, a와 b의 최대공약수 = b와 r의 최대공약수

 

 

예제에 나온 24, 18 에 대해서 최대공약수를 구해보자

 

단계 1

 

a = 24, b = 18

=> r= 6

 

GCD(24,18) = GCD(18,6)

 

단계 2

 

a = 18, b = 6

=> r = 0

 

r 이 0보다 크거나 같아야 하므로

여기서 멈춘다.

 

r= 0 이라는 뜻은,

18을 6으로 나눈 나머지가 0이라는 것이다.

즉, 18이 6으로 나누어 떨어진다는 것이다.

때문에 6이 18과 6의 최대공약수가 된다.

 

GCD(18,6) = GCD(6,0) = 6

 

단계 3

 

위의 과정을 정리하면

 

GCD(24,18) = GCD(18,6) = GCD(6,0) = 6

 

즉 24와 18의 최대공약수는 6이 된다.

 

 

 

최대공약수를 구하는 코드는 2가지가 있다.

 

반복문 방식

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

 

재귀 방식

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

 

 

 

2) 최대공배수 : LCM

 

a = AD

b = BD 

라고 하자.

 

즉, D는 최대공약수이다.

그러면 A와 B는 서로소이다.

 

최대공배수는 ABD 가 되어야 한다.

 

이때

a*b/ 최대공약수

= ABDD/ D

= ABD 

 

즉, 최대공배수가 나온다.

 

그래서 gcd 가 최대공약수를 나타내는 메소드라고 할 때 

코드로 다음과 같이 나타낼 수 있다.

 

 

코드

 

	
	public static int lcm(int a, int b) {
		return a*b/gcd(a,b);
	}

 

 

 

2. 최종 코드

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		
		int one= Integer.parseInt(st.nextToken());
		int two= Integer.parseInt(st.nextToken());
		
		System.out.println(gcd(one, two));
		System.out.println(lcm(one,two));
		
	}
	
	
	public static int gcd(int a, int b) {
		
		if(b==0) {
			return a;
			
		}else {
			return gcd(b, a%b);
			
		}
	}
	
	
	public static int lcm(int a, int b) {
		return a*b/gcd(a,b);
	}
}

 

참고 자료 :

 

https://st-lab.tistory.com/154#algorithm