최대공약수 구하기 알고리즘

최대공약수를 구하는 알고리즘은 '유클리드 호제법'을 이용한 알고리즘이 있습니다. 이 알고리즘을 쓰면 최대공약수를 빠르게 알 수 있고, 이를통해 최소공배수까지 알 수 있습니다.

---

1.최대공약수 구하기

이 알고리즘의 원리는 다음과 같습니다.

1. 2개의 자연수 A와 B의 숫자가 있습니다.
2. A를 B로 나눈 나머지를 구합니다.
3. 그 다음 나눈 나머지가 0이 아닌 경우에는 A자리에 B를, B자리에 나머지를 넣고 0이될 때 까지 2과정을 반복합니다.
4. 나눈 나머지가 0이 됐을때 B가 최대공약수가 됩니다.

숫자를 예로 설명하겠습니다.
1071과 1029의 최대공약수를 구하면
1. 1071과 1029의 나머지는 42
2. 1029와 42의 나머지는 21
3. 42와 21의 나머지는 0
즉 1071과 1029의 최대공약수는 21입니다.

Algorithm.java

public class Algorithm {

    static int GCD(int a, int b){ // 최대공약수 구하기 재귀함수 
        if(b == 0){ // 나머지가 0일경우 a가 최대공약수 
            return a;
        }else{
            return GCD(b, a%b);
        }
    }


    public static void main(String[] args) {
        int x = 1071;
        int y = 1029;
        System.out.println( GCD(x,y) ); // 21
    }
}

C++

#include <iostream>
#define endl '\n'
using namespace std;

int GCD(int a, int b){
    if(b == 0){
        return a;
    }else{
        return GCD(b, a%b);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int x = 1071;
    int y = 1029;
    cout << GCD(x,y); // 21
}

위와 같은 방법을 이용하면 최악의 경우라도 십진법으로 표시한 자리수의 5배를 반복하기전에 최대공약수를 찾을 수 있습니다.
즉 O(logN)입니다.

---

2.최소공배수 구하기

최소공배수는 최대공약수를 구했다면 간단하게 구할 수 있습니다.
두수의 곱을 해준 뒤 최대공약수만큼 나눠주면 최소공배수가 됩니다.

위의 수 1071이랑 1029를 예로 하자면 다음과 같습니다.

최소공배수 = 1071 * 1029 / 21; // 52479