유클리드 호제법 - 최대공약수 구하기 (자바스크립트 코드)

유클리드 호제법 (유클리드 알고리즘)

두 양의 정수 혹은 다항식의 최대공약수를 구하는 방법이다. 두 자연수 a,b에 대해 

r = a % b
gcd(a,b) = gcd(b,r)

r을 a를 b로 나눈 나머지로 정의할 시 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

그럼 b와 r의 최대공약수를 구해야 하는데 이때 b를 r로 나눈 나머지를 r2라고 할 경우, b와 r의 최대공약수는 r과 r2의 최대공약수와 같다. 만약 r을 r2로 나눈 나머지값이 0일 경우 r2가 최대공약수이다.

만약 그렇지 않을 경우, 위와 같은 과정을 나머지 값이 0이 나올 때까지 반복하여 최대공약수를 구한다.

예시를 보자.

a = 56, b = 21 이 두 수에 대한 최대공약수 gcd(56, 21) 를 구하여 보자. 우선 a를 b로 나눈 나머지 값을 알아보자.

r(a를 b로 나눈 나머지 값) = 56%21 = 14

이번엔 b을 r로 나눈 나머지를 구해보자.

r2 = 21 % 14 = 7

이번엔 나머지 r2 = 7을 구하였다. 이제 r을 r2로 나눈 나머지를 구해보자.

r3 = 14 % 7 = 0

나머지 값이 0이 되었다.

나머지 값이 0이 나올 때까지 위와 같은 과정을 거쳐서 gcd(56, 21) = 7 임을 알 수 있다.

 

자바스크립트 코드

1️⃣ 유클리드 호제법을 이용하지 않았을 때

function gcd(a,b){
	let num = Math.min(a,b);
	while(num > 0){
    	if(a%num === 0 && b%num === 0){
        	return num;
        }
        num--;
    }
    return 1;
}

2️⃣ 유클리드 호제법을 이용한 코드 ⭐️

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

 

📹 참고하면 좋은 영상