유클리드 호제법 (최대공약수, +최소공배수)

유클리드 호제법이란 두 정수의 대해서 최대공약수를 찾아내는 알고리즘입니다. 

 

 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a> b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다.

const greateat_common = (a,b) => {
    if(b === 0) return a
    return greateat_common(b, a%b);
}
console.log(greateat_common(10,20));

재귀 함수로 풀어보았습니다. 두 정수 a b를 할당받습니다. 최대공약수를 구할 때 하나의 값이 0이면 다른 값이 최대공약수가 됩니다. 이조건을 만족하기 위해 b가 0이면 a를 반환해줍니다. 반대 상황일 때도 루프를 한 번 돌고 반대 측 값이 반환됩니다. a에는 b값을 할당하고, b에는 a를 b로 나눈 나머지 값을 넣습니다. b가 0이 될 때까지 반복하다가 0이 되면 a값을 반환합니다. 이때 이 값이 최대공약수가 됩니다. 

const greateat_common = (a,b) => {
    if(b === 0) return a
    return greateat_common(b, a%b);
}
console.log(greateat_common(10,20));

const least = (a,b) => (a*b) / greateat_common(a,b); //최소공배수

+ 여기서 최소공배수를 구하고 싶다면 [최대공약수 = (a*b)/최소공배수]를 사용하여 구하면 됩니다.