[Algorithm] 유클리드 호제법(최대공약수 gcd) 알아보기

 

1. 유클리드 호제법이란?

유클리드 호제법(- 互除法, Euclidean Algorithm)

 

유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘 중 하나이며, 두 개의 정수 or 다수의 자연수에서 최대공약수(gcd)를 구하는 방법입니다.

 

이때 호제법이라는 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘을 의미합니다.

 

 

2. 유클리드 호제법으로 최대공약수 구하기

 

나머지가 0이 될때까지 계속 재귀적으로 구해줘야합니다.

 

1. a, b (a> b) 두 수를 큰 수를 작은 수로 나눠 나머지(R1)를 구합니다.  R1 = (a % b), R1!= 0
2. b % R1을 나눠서 나머지(R2)를 구합니다. R2!= 0
3. R1 % R2을 나눠 나머지(R3)를 구합니다. R3 = (R1 % R2) , R3!= 0
4. R2 % R3을 나눠 나머지(R4)를 구합니다. R4 = (R2 % R3) , R4 == 0

그러면 두수 a와 b의 최대공약수(gcd)는 나머지가 0이기 전 값인 R3가 됩니다.

 

a = 7 , b = 20

 

1. 20 % 7 → 나머지 : 6

 

2. 7 % 6 → 나머지 : 1

 

3. 6 % 1 → 나머지 : 0

 

나머지가 0이 되기 전 나머지 1이 최대공약수 (gcd)가 됩니다.

---

 

a = 12 , b = 222

 

1. 22 % 12 → 나머지 : 10

 

2. 12 % 10 → 나머지 : 2

 

3. 10 % 2 → 나머지 : 0

 

나머지가 0이 되기 전 나머지 2가 최대공약수 (gcd)가 됩니다.

 

 

3. 유클리드 호제법 구현  (js)

function gcd(a, b) {
    if (b === 0) return a;
    
    return gcd(b, a % b);
  }