[알고리즘] 최대 공약수(GCD) 구하기 - C, Java, Python

최대 공약수 구하기에 대해서 알아보겠습니다.

목차

1. 최대공약수(GCD)

2. 최대공약수(GCD) 구하기

3. 유클리드 호제법

4. Code - C, Java, Python

1. 최대공약수(GCD)

---

정수의 성질 중 하나로 먼저 공약수란, 두 수 혹은 그 이상의 여러 수의 공통인 약수라는 뜻입니다. 그래서 최대공약수 ( greatest common divisor  -  GCD ) 는 공약수 중 가장 큰 것이라는 뜻입니다.

 

두 수 a, b 의 최대공약수를 수학적 기호로 표시하면, gcd(a,b) 이며,

특히  gcd(a,b) = 1 이면 두 수 a,b 는 서로소 라고 합니다. 

 

2. 최대공약수(GCD) 구하기

---

찾는 법은 간단하다. 약수를 나열하여 공약수를 찾고 그 공약수중에 가장 큰 값을 찾으면 됩니다.

예시로 12, 20 의 최대공약수를 구해봅시다

12 : 1, 2, 3, 4, 6, 12
20 : 1, 2, 4, 5, 10, 20

여기서 공약수는 1,2,4 가 되고 가장 큰 값인 4가 최대공약수(GCD) 가 된니다. 위 예시는 약수의 개수가 적은 편이라 없는 값이라 쉽게 찾았지만 큰 값을 찾으라고 한다면 찾기 어려울 것입니다. 그래서 이 문제를 해결하기 위한 방법으로 유클리드 호제법이 있습니다. 놀랍게도 기원전에 발견된 인류 최초의 알고리즘 이라고 합니다. 

 

3.유클리드 호제법

---

유클리드 호제법은 유클리드가 기원전 3세기에 집필한 책 유클리드 원론에서 알 수 있습니다. 기하학과 정수론을 다루고 있는데 직접 만든 것은 아니고, 당대에 알려져 있는 수학에 관한 내용을 모아놓은 책이라고 합니다. 

 

알렉산드리아 유클리드(Euclid of Alexandria)

 

두 자연수 a, b에 대하여 a를 b로 나눈 나머지를 r 이라고 하면, a와 b의 최대공약수(gcd)와 b와 r의 최대공약수(gcd)는 같다는 성질을 이용하는 방법입니다. b 를 r로 나눈 나머지를 계속해서 나누어 나머지를 계산하는식으로 최대공약수(gcd)를 구할 수 있게 된니다.  계속 나누다가 나머지가  0이 되는 순간에 값을 확인하면 됩니다. 

예시로 12, 20 의 최대공약수를 구해봅시다.

20 = 12 * 1 + 8
12 = 8 * 1 + 4
8 = 4 * 2 (나머지가 0 임), 

이러한 방법으로 최대공약수(gcd) 를 구할 수 있습니다. 해당 알고리즘을 코드로 구현을 해보겠습니다.

 

4.Code - C, Java, Python

---

1) C 

int Euclidean(int a, int b)
{
    int mod = a % b;
    while ( mod > 0 )
    {
    	a = b ;
        b = mod;
        mod = a % b;
    }
    
    return b;
}

2) Java

public int Euclidean(int a, int b) {
	int mod = a % b;

	while(mod > 0) {
		a = b;
		b = mod;
		mod = a % b;
	}

	return b;
}

3) Python

def Euclidean(a, b):
    while mod != 0:
        mod = a % b
        a = b
        b = mod
    return a