[ 알고리즘 ] 유클리드 호제법

失礼だが、純愛だよ

유클리드 호제법

최대공약수(GCD) , 최소공배수(LCM)를 구할떄는 유클리드 호제법을 쓰는게 제일 구현하기 간단함.

유클리드 호제법은 최대공약수를 구하는 알고리즘인데, 최소공배수는 그냥 두 수를 곱한 뒤에 최대공약수를 나누면 되니까,, 뭐 그렇게 구현하면 된다

 

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

 

라고 나무위키에 나와있는데 간단히 설명하면

 

-  a 와 b의 나머지(r1)를 구하고 (a>b)

-  r1 과 b의 나머지(r2)를 구한다.

-  r1 과 r2의 나머지...  를 계속 반복

- 마지막에 나머지가 0이 됐을때 작은놈 최대공약수임

 

=> 이걸 재귀함수로 구현하면 편하겠지?라는 생각

 

+) LCM = a * b / GCD  

이렇게 최소공배수도 구하면 된다.

 

ex) 백준 2609번 - 최대공약수와 최소공배수

import java.io.*;
import java.util.*;
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 a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int min = Math.min(a, b);
		int max = Math.max(a, b);
		//최대공약수
		int gcd = GCD(max,min);
		System.out.println(gcd);
		
		//최소공배수
		System.out.println(max*min/gcd);
	}
	static int GCD(int max, int min) {
		if(max%min==0) {
			return min;
		}else {
			return GCD(min, max%min);
		}
	}
	//재귀함수로 구현
	//둘의 나머지가 0이면 min이 gcd
	//나머지가 0이 아니면, min 과 나머지의 GCD로 돌림

}

 

Related Problems :)

백준 1850번 - 최대공약수

백준 1934번 - 최소공배수

백준 13241번 - 최소공배수