최소공배수, 최대공약수

최소공배수와 최대공약수를 구하는 공식이 있다.
유클리드 호제법이라는 건데,
이를 코드로 구현된 내용을 복습하고자 한다.

최대공약수 (gcb)

int gcb(int a, int b)
{
	int c;
    while(b != 0)
    {
    	c = a % b;
        a = b;
        b = a;
    }
    return a;
}

예를 들어, 6과 4의 최대공약수를 구하고자 한다면
a = 6, b = 4
(b가 0이 아니므로)
c = 6 % 4 -> 2
a = b -> 4
b = c -> 2
(또 b가 0이 아니므로)
c = 4 % 2 -> 0
a = b -> 2
b = c -> 0
(이번엔 b가 0이므로) return a; -> 2

따라서 2가 6과 4의 최대공약수가 된다.

최소공배수 (lcm)

int lcm(int a, int b)
{
	return a*b / gcb(a, b);
}

최소공배수는 위에서 구한 gcb함수를 이용하면 구할 수 있다.

++
배열의 맨 뒷 값을 받아오기 위해서는,
vector.back() 함수를 이용하면 된다.
(pop_back()은 단순히 맨 뒷 값을 빼서 삭제하는 것)

헷갈리지 말기!!