[Javascript] 최대공약수 구하기 (유클리드 호제법)

seoyeon·2023년 4월 25일

JavaScript TIL 유클리드 호제법 자바스크립트

Javascript 공부하기

목록 보기

13/20

저는 수포자였는데.. 이렇게 또 수학을 만나네요..
졸업하면 다시는 쓸 일이 없을 줄 알았는데..🥲

눈물을 머금고.. 유클리드 호제법으로 최대공약수 구하는 방법을 알아볼게요..!
(위의분 표정이.. 나랑 똑같네..😞)

📌 최대공약수

두 수의 공통된 약수 중에서 가장 큰 수

Example

4의 약수 - 1, 2, 4
16의 약수 - 1, 2, 4, 8, 16
→ 4와 16의 최대공약수는 4이다.

학교 다닐때는 최대공약수를 소인수분해를 이용해서 구하곤 했었는데 자바스크립트에선 유클리드 호제법 을 이용해서 구해볼거에요!

📌 유클리드 호제법

두 수의 최대공약수를 구하는 알고리즘

유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이에요. 😯

호제법이란? 두 수가 서로 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.

사용방법

1. 큰 수를 작은 수로 나눈 나머지를 구한다. (72 % 30)

2. 나누었던 수(B)와 그 나머지(A % B의 결과인 12)로 다시 나머지 연산을 한다.

3. 이 과정을 나머지(A % B)가 0이 될 때까지 반복하며, 0이 된 시점에서의 첫 피연산자(B=6)가 최대 공약수가 된다.

예시 : 72와 30의 최대공약수를 유클리드 호제법을 이용해서 구하는 방법을 테이블로 표현하면 아래와 같다.

GCD(A, B)	A	B	A % B
GCD(72, 30)	72	30	12
GCD(30, 12)	30	12	6
GCD(12, 6)	12	6	0

A % B가 0이 되는 순간 B의 값이 최대 공약수 가 됩니다.
위 테이블로 봤을 때는 A % B가 0이 되는 시점의 B가 6이 되므로 최대 공약수가 6임을 확인할 수 있습니다.

따라서 A > B라고 할 때 B가 0이 될 때까지 나머지 연산을 수행하도록 하면 됩니다.
이는 반복문 이나 재귀함수 를 이용하는 방법이 있습니다. 저는 재귀함수로 구해보겠습니다!

JavaScript로 구현하기

// 두 수 a, b를 넣는다.
function gcd(a,b){
  	// b(나머지)가 0이면 a(직전 나머지)를 반환하고 탈출
	if(b === 0){
    	return a;
    }
  	// b를 a로 보내고 a % b를 나눈 나머지를 매개변수 b로 넣어서 재귀함수로써 호출
  	return gcd(b, a % b);
};