최대공약수 ( gcd ) & 최소공배수 ( lcm )

 

 

 

Algorithm

 

 

What ?

최대공약수 ( gcd  ) & 최소공배수 ( lcm )

최대 공약수 ( gcd ) :  두 자연수의 공통된 약수인 공약수 중 가장 큰 공약수

   최소 공배수 ( lcm ) : 두 자연수의 공통된 배수인 공배수 중 가장 작은 공배수

 

---

 

How ?

유클리드 공식 ( Euclidean algorithm ) 으로 도출한다.

💡  유클리드 공식 (Euclidean algorithm) ❓

두 양의 정수 a와 b가 존재하고 (a > b)
a = bq + r (0 ≤ r < b)이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다.
r = 0이라면, a, b 의 최대공약수는 b가 된다.

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

 



Example

24 와 18 의 최대공약수 구하기

function main() {
	let a = 24;
    let b = 18;
	const result = gcd(a,b);
    
    console.log("최대공약수 : " + result ); // 최대 공약수를 호출
	console.log("최소공배수 : " + (a*b)/res); // 최소공배수
}

// 최대공약수 함수
function gcd(a, b) {
	let num = 0;
    
	if(a < b) {
    	num = b % a
    }else{
    	num = a % b
    }
 
	if(num === 0) return a < b ? a : b
    
	return gcd(a < b ? a : b , num);
}

 

 

Detail

 

1. 주어진 값에서 큰 값 % 작은 값으로 나머지를 구한다.
   
   
2. 나머지가 0이 아니면, 작은 값 % 나머지 값을 재귀함수로 계속 진행
   
   
3. 나머지가 0이 되면, 그때의 작은 값이 ' 최대공약수 '이다.
   
   
4.  주어진 값들끼리 곱한 값을 '최대공약수'로 나눈 값이 '최소 공배수 '이다.

---