JS, 최대공약수 최소공약수 구하기

최대공약수를 구할때 기본적으로 반복문을 돌려서 최대공약수를 구할수 있으나

유클리드 호제법을 이용하여 구하면 쉽게 간단하게 구할 수 있음

 

유클리드 호제법

두 수의 최대공약수를 구하는 알고리즘

 

2개의 자연수 A, B에 대하여 A를 B로 나눈 나머지를 r이라고 한다면(단, A>B)

A와 B의 최대공약수는 B와 r의 최대공약수와 같음

 

이 성질에 따라 B를 r로 나눈 나머지를 r'을 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여

나머지가 0이 되었을때 나누는 수가 A와 B의 공약수

 

예시

유클리드 호제법으로 24, 15의 최대 공약수 구하기

24 % 15 = 9

          15 % 9 = 6

                   9 % 6 = 3

                          6 % 3 = 0

구현

function gcd(a, b){
    return (a % b) === 0 ? b : gcd(b, a % b);
}

 

유클리드 호제법을 이용하여 최소 공배수 구하기

최소공배수는 최대공약수와 밀접한 관계가 있는데

정수 a, b의 최대공약수 G = gcd(a, b)에 대하여 아래의 식을 만족하는 정수 x와 y가 존재함

a = Gx, b = Gy (단, x, y는 정수)

 

이 때 a * b = GGx*y 임을 알 수 있고 G는 두 수의 최대 공약수이며 x와 y는 서로소인 관계를 가짐

집합적으로 생각하면 a와 b의 합집합은 G, x, y이고 이 세 수를 곱한 Gxy가 최소공배수가 됨을 알 수 있음

 

• a * b = GGx*y
• a * b / G = GGx*y / G (양변에 최대 공약수를 나누어 줌)
• a * b / G = Gxy(최소공배수)

결론적으로 최소공배수 = a * b / G

 

구현

function lcm(a, b){
    return a * b / gcd(a, b);
}