최대 공약수 구하기 | GCD | Greatest Common Divisor

const getGCD = (num1, num2) =>{
	let gcd = 1;
    for(let i =1; i<= Math.min(num1,num2); i++){
    	if(num1 %i === 0 && num2 %i ===0 ){
        	gcd = i;
        }
    }
    
    return gcd;
}

---

 

1. 최대공약수를 구해보자

2. 최대공약수란 두 수를 동시에 나눌 수 있는 가장 작은 숫자이다.

3. 우선 최대공약수가 궁금한  num1, num2를 두개 받는다. 

4.  두 수에 최대공약수는 1부터 시작한다. ( 동시에 나눌 수 있는 가장 작은 수는 1이다.)

5.  for loop안에서 i는 1부터 시작한다. 

6. i 는 num1, num2 두 숫자 중에서 더 작은 수 까지 loop를 반복할 수 있다. (예 : 4, 8 일때 4까지)

7. for loop는 1씩 증가한다.

8. num1 % i 와 num2% i를 동시에 나눠서 나머지가 0일때 -> 두 숫자 다 나눠질때를 의미한다. -> 최대공약수이다. 

9. 그렇다면 i를 gcd에 해준다.

10. 그리고 gcd를 리턴한다.

 

---

다른 좋은 방법을 찾아보자..

---

✨ 유클리드 호제법 ✨ 

2개의 자연수의 최대공약수를 구하는 알고리즘이다.

a>b일때 a를b로 나눈 나머지를 r이라고 할때

GCD(a,b) ===GCD(b,r)은 같고

r이 0이면 이때 b가 최대공약수다. 

 

GCD(24,16) -> 일때 24를 16으로 나눈 나머지는 8이다.

그러면 GCD(16,8) 이 되고

GCD(16,8) -> 일떄 16을 8로 나눈 나머지는 0이된다.

나머지가 0이 됐을때 나눈 8, r이 최대공약수가 되는것이다.

const getGCD = (num1, num2) => {
	if(num2===0) return num1;
    else return getGCD(num2,num1%num2)
}

 

---

유클리드 호제법 보다가 내가 푼거 보니까 넘 길어보인다--;