짹뚜 스튜디오

유클리드 호제법은 두 수의 최대공약수를 구할 때 사용하는 알고리즘이다. 일반적으로 두 수의 최대공약수를 구하려면 일단 두 수를 소인수분해한 후 공통된 소수 중 가장 큰 수를 찾으면 된다. 그러나 수가 커질수록 소인수분해하기 어렵기 때문에 유클리드 호제법을 사용하면 쉽고 효율적으로 구할 수 있다. 구현 방법 유클리드 호제법의 개념은 다음과 같다. 두 자연수 a와 b (a > b), 그리고 a를 b로 나눈 나머지 r이 있을 때, a와 b의 최대공약수는 b 와 r의 최대공약수와 같다. GCD(a, b) = GCD(b, r) 위와 같은 방법을 반복해서 r이 0이 될 때 b가 최대공약수가 된다. 이 알고리즘의 시간복잡도는 O(log N)이 된다. 재귀 함수를 사용하면 쉽게 구현할 수 있다. //javascript..