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

 

최대 공약수

만약 12, 18의 최대 공약수를 찾고자 한다면, 간단하게 두 수의 약수를 모두 나열한다.

12:1, 2, 3, 4, 6 ,12

18:1, 2, 3, 6 ,9 ,18

12와 18의 공약수중 가장 큰 수인 6이 최대 공약수가 된다.

다만 이 방법으로 큰 수들의 최대공약수를 찾으려면 매우 오랜 시간이 걸릴 것이다.

따라서 유클리드 호제법으로 해결하면 된다.

유클리드 호제법

두 양의 정수 a,b (a>b)에 대하여 a=bq+r(0≤r<b)이라 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다.

gcd⁡(𝑎, 𝑏)=gcd⁡(𝑏, 𝑟)

즉, 𝑟=0이라면, 𝑎,𝑏의 최대공약수는 b가 된다.

 

위의 정리를 활용하면 최대 공약수를 간단하게 구할 수 있다.

한마디로 r이 0이 될 때까지 계속해서 a에 b값을 다시 넣고, r을 b에 대입하면 된다.

 

구현방법은 총 2가지가 있다.

1. 반복문

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

b의 값이 0이 될 때까지, a를 b로 나눈 나머지를 b에 대입하고, a와 b의 값을 교환합니다.

2. 재귀함수

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

위와 동일하게 b의 값이 0이 될때까지 재귀함수를 반복합니다.

최소공배수 

예를 들어 두 수 10,12의 공배수를 찾고자 한다면 두 수를 소인수분해를 하여 최소공배수를 찾을 수 있다.

10= 2 x 5

12=2² x 3

중복되는 소인수는 차수가 큰 횟수만큼, 그리고 나머지 소인수를 모두 곱해주면 최소공배수를 구할 수 있다.

위의 예시에서는 2를 두 번, 3을 한번, 5들 한번 곱한 값, 즉 60이 최소 공배수가 된다.

 

여기서 중복되는 소인수는 위에서 구한 최대공약수이므로

 

a*b를 최대공약수로 나눈 값이 최소공약수이다.