유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
b
가 0
이 될 때까지 계속해서 재귀 호출을 해주고, 0이 되면 a
를 반환한다.
// 단, a가 b보다 커야함.
function gcd(a, b) {
return b ? gcd(b, a % b) : a;
}
// 단, a가 b보다 커야함.
function gcd(a, b) {
while (b > 0) {
let tmp = a;
a = b;
b = tmp % b;
}
return a;
}
106과 16의 최대공약수 - gcd(106, 16)
SEQ | gcd(a, b) | a | b | a % b(remainder) |
---|---|---|---|---|
1 | gcd(106, 16) | 106 | 16 | 10 |
2 | gcd(16, 10) | 16 | 1 | 6 |
3 | gcd(10, 6) | 10 | 6 | 4 |
4 | gcd(6, 4) | 6 | 4 | 2 |
5 | gcd(4, 2) | 4 | 2 | 0 |
a % b
가 0
이 되면 b
의 값 2
가 최대공약수가 된다.
최소공배수 = 두 자연의 곱 / 최대공약수
위의 예시로 106과 16의 최소공배수는 848 (106 * 16 / 2)
이 된다.
function calculator(n, m) {
const num = gcd(n, m);
return [num, (n * m) / num];
}
function gcd(a, b) {
return b ? gcd(b, a % b) : a;
}
console.log(calculator(106, 16)); // [2, 848]