[Algorithm] 유클리드 호제법

1. 개요

- 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나.

 

2. 방법

1. 입력으로 두 수 m,n(m>n)이 들어온다.

2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.

3. m이 n으로 나누어 떨어지면 n을 출력하고 알고리즘을 종료한다.

4. 그렇지 않으면 m을 n으로 나눈 나머지를 새롭게 m에 대입하고 , m과 n을 바꾸고 3번으로 돌아온다.

 

3. 구현

- C++

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

 

4. 예시 문제

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

 

 

출처: 위키백과, 백준