GCD / Euclidean algorithm

• 2개의 자연수의 최대 공약수(Greates common divisor)를 구하는 알고리즘
• 대표적인 gcd를 구하는 가장 간단한 방법은 2부터 min(a, b)까지 모든 정수로 나누는 방법이 있다.
  • 이경우 시간 복잡도는 O(N).
  • 유클리드 호제법을 사용하면 자연수 a, b가 주어질때, a%b가 0이 아니면 a와 b를 바꾼다. 이후 나머지가 0일떄까지 반복하며, a%b가 0일때 b가 최대 공약수(나누는 수!).
  • 이경우 시간 복잡도는 O(Log N).

• 원리를 다시 설명하자면 두 수 A와 B가 존재할 때(A>=B), A, B의 최대 공약수를 구하려면 A를 B로 나눈다. 이를 식으로 나타내면 A = QB + R (Q=임의의 수 몫, R=나머지)로 나타낼 수 있다.
• 이 후 A와 B의 최대 공약수 대신 B와 R의 최대 공약수를 구하면 같은값이 나온다.
  • 이를 나머지가 0이 될때까지 반복한 후 나머지가 0이 된다면 이때 작은수가 최대공약수이다.

Recursion

// Greatest common divisor (a>=b)
int gcd(int a, int b) {
  if(b==0) return a;
  return gcd(b, a%b);
}

While loop

// Greatest common divisor
int gcd(int a,int b) {
    while(1){
        int r = a%b;
        if(r==0) return b;
        a = b;
        b = r;
    }
}

LCM

• 번외로 Lowest common multiple(최소 공배수)를 구하는 코드.

// Least common multiple
int lcm(int a, int b) {
    return (a/gcd(a, b)) * b;
}

GitHub source code

• https://github.com/kon6443/Algorithms/tree/main/Algorithm/GCD_LCM