유클리드 호제법

유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 방법이다.

최대 공약수(GCD)

어떤 두 수 A,B가 존재할 때, 공통인 약수 중 가장 큰 수를 말한다.

EX) GCD(A,B) = A와 B의 최대공약수

최소 공배수(LCM) 

어떤 두 수 A,B가 존재할 때, 그들의 배수가 되는 가장 작은 수 

최대 공약수(GCD) 구하는 방법 

출처 :  http://yoonbumtae.com/?p=2302

 

유클리드 호제법으로 최대 공약수 구하는 방법

유클리드 호제법의 핵심은 모듈러 연산이다.

모듈러 연산을 반복해서 0이 될 때까지 간다면 최대공약수를 구할 수 있다.

출처: https://wonit.tistory.com/411

1. A와 B중 더 큰수를 찾고, 큰수를 A로, 작은수를 B로 설정한다.
2. A % B = N을 구해서, N==0이면 B는 최대공약수이다.
3. N !=0 이면 A=B, B=N으로 대입하고, 과정을 반복한다.

유클리드 호제법으로 최소 공배수 구하는 방법

 

출처: https://wonit.tistory.com/411

최소 공배수의 핵심은 GCD이다.

유클리드 알고리즘을 통해서 구한 최대 공약수에 a와 b를 각각 곱한 값을 나눠준다면 최소공배수를 구할 수 있다.

자바로 구현

최대 공약수 구하기 (반복문)

	private static int gcdByLoop(int a, int b) {
		if(a<b) {
			int temp = a;
			a = b;
			b = temp;
		}
		while(b>0) { //b가 0이되면 종료 
			int temp =b;
			b = a%b;
			a = temp; // b였던게 a가 된다.
		}
		return a;
	}

최대 공약수 구하기 (재귀)

private static int gcdByRecursive(int a,int b) {
		if(a<b) { //큰수에 a가 들어가야한다. 
			int temp = a;
			a = b;
			b = temp;
		}
		if(b==0) {
			return a;
		}
		return gcdByRecursive(b, a%b);
	}

 

최소 공배수 구하기 

	private static int getLcm(int a,int b) {
		return (a*b) / gcdByLoop(a,b);
	}

 

---

출처: https://wonit.tistory.com/411