A와 B의 공통된 약수 중에 가장 큰 정수를 최대 공약수라고 한다.
// O(N)
const getGCD = (A, B) => {
let gcd = 1;
for(let i = 2; i <= Math.min(A, B); i++) {
if(A % i === 0 && B % i === 0) {
gcd = i;
}
}
return gcd;
}
2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
유클리드 호제법의 기본 원리는 A
를 B
로 나눈 나머지를 R
라고 했을 때, GCD(A, B) = GCD(B, R)
과 같다는 것이다.
R
이 0
이라면, 그 때의 B
가 최대 공약수이다.
A = 24
, B = 16
이라고 가정해보자.
GCD(24, 16) = GCD(16, 8) = GCD(8, 0)
GCD = 8
const getGCD = (A, B) => B ? getGCD(B, A % B) : A;
// 여기서 A < B의 경우에는 값이 자동으로 스왑된다.
재귀로 접근하지 않는다면 아래와 같이 구현한다.
시간복잡도 : O(logN)
const getGCD = (a, b) => {
while(b !== 0) {
let r = a % b;
a = b;
b = r;
}
return a;
}
두 수 또는 그 이상의 여러 수의 공통인 배수 중 가장 작은 수.
a
와 b
의 최소 공배수는 a
와 b
의 곱을 a
와 b
의 최대 공약수를 나눈 것과 같다.lcm = (a*b) / gcd
.a * b = gcd * lcm
과 같다는 원리를 이용하는 것이다.function lcm(a, b) {
return (a * b) / gcd(a, b);
}
function gcd(a, b) {
while (b !== 0) {
let r = a % b;
a = b;
b = r;
}
return a;
}
function solution(n, m) {
//const gcd = (a, b) => {
//if(b === 0) return a;
//return gcd(b, a % b);
//};
const gcd = (a, b) => b ? gcd(b, a % b) : a;
const lcm = (a, b) => a * b / gcd(a, b);
return [gcd(n, m), lcm(n, m)];
}