[JAVA SCRIPT] 유클리드 호제법

1. 유클리드 호제법

두 수의 최대공약수를 구하는 알고리즘
두 수가 서로 상대방의 수를 나눠서 결국 원하는 수를 얻는 알고리즘

---

2. 예시: 150과 108 최대공약수 구하기

일반적

최대공약수를 구하기 위해서 소인수분해를 해야한다.

150 = 5 X 5 X 2 X 3 

108 = 2 X 2 X 3 X 3 X 3

두 수를 소인수분해하고 공통된 소수 = 최대공약수 또는 GCD라고 한다.
그럼 150과 108 최대공약수는 2 X 3인 6

하지만 일반적인 방법은 숫자가 커질수록 약수의 개수도 많아지고 시간이 오래걸린다.

---

유클리드 호제법 사용하기

유클리드 호제법을 사용하기에 앞서, MOD 연산에 대해 알아야한다.

MOD 연산: 두 값을 나눈 나머지를 구하는 것

1. 큰 수를 작은수로 나눈 나머지, MOD 연산을 한다

150 % 108 = 42 

2. 나눴던 수와 나머지로 다시 연산

108 % 42 = 24

3. 나머지가 0이 될때까지 계속 반복

42 % 24 = 18

24 % 18 = 6

18 % 6 = 0

마지막 계산에서 나누는 수로 사용된 숫자가 최대공약수!

계속 mod(%) 연산을 0이 될때까지 하면 된다.
그러니까, A > B 이면 B가 0이 될때까지 나머지 연산을 수행하면 된다!

---

3. 코드

C언어 반복문

int GCD(int a, int b){
  int tmp;
  while(b){      //b가 0이 될 때까지
    tmp = a % b;
    a = b;
    b = c;
  }
  return a;
}

C언어 재귀함수

int GCD(int a, int b){
  return b ? GCD(b, a % b) : a;
}

자바스크립트

// 두 수 a, b를 넣는다.
function gcd(a,b){
  //나누는 코드 
	if(b === 0){
    	return a;
    }
  	// b를 a로 보내고 a % b를 나눈 나머지를 매개변수 b로 넣어서 재귀함수로써 호출
  	return gcd(b, a % b);
};

---

최대공약수 문제를 풀때 도움이 되었으면 해서 남기는 포스트이다
문제 풀고싶다면 아래 문제를 풀어보길 바란다.
최대공약수 문제