최대공약수

[기초 알고리즘] 최대공약수 최소공배수 찾기(유클리드 호제법) - 자바스크립트

유클리드 호제법 유클리드 호제법이란, 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다. 유클리드 호제법에 의하면 A와 B 두 수의 최대공약수를 구할 때, A = Bq+r의 식으로 만든 뒤 B와 r의 최대공약수를 구하는 문제로 바꿀 수 있다. 연속되는 B, r의 최대공약수에 대해서도 B = rq+r2 와 같이 재귀가 가능하다. 최대공약수는 A,B 모두 나누어 떨어뜨리는 최대의 약수이므로, r=0 일 때 B의 값이 최대공약수이다. 최대공약수 구하기 유클리드 호제법을 이용해 최대공약수를 구해보자. 반복문 사용하기 function gcd(a,b){ let c = 0; while(b !== 0){ c = a % b; a = b; b = c; } return a; } 재귀함수로 만들기 function gc..