[알고리즘] 최대공약수, 최소공배수

유클리드(Euclid) 알고리즘

---

최대공약수

최대 공약수는 2개 이상의 자연수의 공약수 중에 가장 큰 수를 말한다.

 

이 알고리즘은 '2개의 자연수 중 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다.'

는 성질을 이용하여 최대공약수를 찾는 것이다.

예제) 24와 14의 최대공약수
24, 14
24 - 14, 14 = 10, 14
14 - 10, 10 = 4, 10
10 - 4, 4 = 6, 4
6 - 4, 4 = 2, 4
4 - 2, 2 = 2, 2
2 - 2, 2 = 0, 2
= 최대공약수 2

위 예제와 같이 최대공약수는 주어진 두개의 수에서 큰 수를 작은수로 계속 뺄셈을 하며 남은 수가 존재하지 않을때까지 진행한다.

 

이는 다음과 같은 코드로 변경 가능하다.

private int GCD(int a, int b)
{
    return (a % b == 0 ? b : GCD(b, a % b));
}

* bool 값은 0을 제외한 수는 모두 참이 된다.
예제) 24와 14의 최대공약수

1. '24 % 14 = 10'이므로, 삼항연산자에서 '거짓'이 된다.
2. GCD(14, 24 % 14) = GCD(14, 10)
3. '14 % 10 = 4'이므로, 삼항연산자에서 '거짓'이 된다.
4. GCD(10, 14 % 10) = GCD(10, 4)
5. '10 % 4 = 2'이므로, 삼항연산자에서 '거짓'이 된다.
6. GCD(4, 10 % 4) = GCD(4, 2)
7. '4 % 2 = 0'이므로, 삼항연산자에서 '참'이되어 최대공약수 'b = 2'를 반환한다.

* bool 값은 0을 제외한 수는 모두 참이 된다.
예제) 21와 6의 최대공약수
1. '21 % 6 = 3'이므로, 삼항연산자에서 '거짓'이 된다.
2. GCD(6, 21 % 6) = GCD(6, 3)
3. '6 % 3 = 0'이므로, 삼항연산자에서 '참'이되어 최대공약수 'b = 3'을 반환한다.

 

 

최소공배수 찾기

---

최소공배수는 2개 이상의 자연수 중 공통된 배수 중 가장 작은 수를 말한다.

예제) 24와 14의 최소공배수
24, 14

배수 방식 :
• 24의 배수 : 24, 48, 72, 96, 120, 144, 168, 192, 216, 240 ...
• 14의 배수 : 14, 28, 42, 56, 70, 84, 98, 112, 126, 140, 154, 168, 182, 196, 210 ...

소인수분해 방식 :
• 24의 소인수 분해 = 2 x 2 x 2 x 3
• 14의 소인수 분해 =2 x 7
2 x 2 x 2 x 3 x 7 = 168

예제와 같이 최소공배수는 다양한 방식으로 구할 수 있지만 가장 흔히 소인수분해 방법을 사용한다.

 

최소공배수를 코드로 변경하면 다음과 같다.

private int LCM(int a, int b)
{
    return (a % b == 0 ? b : GCD(b, a % b));
}

예제) 24와 14의 최소공배수
1. a(24), b(14)를 받는다.
2. 24 % 14 = 10, n = 14
3. 14 % 10 = 4, n = 10
4. 10 % 4 = 2, n = 4
5. 4 % 2 = 0, n = 2
6. (24 * 14) / 2 = 168