[JAVA] 유클리드 호제법_최소공배수, 최대공약수 구하기

유클리드 호제법 이란?

유클리드 알고리즘 (Euclidean algorithm) 은 2개의 자연수의 최대공약수(GCD) 를 구하는 알고리즘 이다.

비교대상인 두 개의 자연수 a와 b에서 (이때, a>b) a를 b로 나눈 나머지를 r 이라고 했을때

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

"r이 0이면 그때 b가 최대공약수이다." 라는 원리를 활용한 알고리즘 이다.

만약 r이 0이 아니라면 a에 b값을 다시 넣고, r을 b에 대입 한 후 다시 반복한다.

 

 

1) 반복문을 이용해서 최대공약수 구하기

  int gcd(int a, int b) { //최대공약수
    while(b!=0) {
      int r=a%b;
      a=b;
      b=r;
    }
    return a;
  }

 

 

2) 재귀함수를 이용해서 최대공약수 구하기

	
	//재귀함수 사용 - 구현이 간단, 코드 간결, 시간 복잡도 O(logN)
	int GCD(int a, int b) { //최대공약수 - 재귀함수 사용
		if(a%b ==0) {
			return b;
		}
		return GCD(b, a%b);
	}
	

 

 

+) 최소공배수 구하기

두 자연수 A,B의 최대공약수가 G, 최소공배수가 L일때
A= a*G, B=b*G (a,b는 서로소) 라고 하면
L=a*b*G
A*B=L*G
두개의 식이 성립. 이를 이용한다.

	int lcm(int a, int b) { //최소공배수
		//L=A*B/G
		//0이 아닌 두 수의 곱 / 두 수의 최대 공약수
		return a*b / gcd(a,b);
	}