[알고리즘] 유클리드 호제법

알고리즘

• 입력으로 두 수 m,n(m>n)이 들어온다.
• n이 0이라면, m을 출력하고 알고리즘을 종료한다.
• m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
• 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

C++코드

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