[알고리즘] 최대공약수/최소공배수

##최대공약수(GCD)

1.구하는 방법

1) 완전탐색

-수 중 제일 작은 수n , 1부터 n까지 나누어 떨어지는 수 구하기

 

2) 완전탐색 (제곱근 까지)

-수 중 제일 작은 수n , 1부터 sqrt(n)까지 나누어 떨어지는 수 구하기

 

3) 유클리드 호제법

-두수 중 하나의 수로 다른 수를 계속 나누는 방법

-시간복잡도: 제일 빠른 방법

int gcd (int a, int b) {
    while (b !=0) {
        int r = a % b;
        a = b;
        b =r;
    }
    return a;
}

##최소 공배수(LCM)

1.구하는 방법

: l = (a/gcd)*(b*gcd)*gcd