유클리드 호제법

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않으나(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다). 정수론을 배우게 된다면 가장 먼저 나올 확률이 높은 공식이다. 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다.

 

최대공약수(GCD)란?
- 두 수의 공통된 "약수 중에서 가장 큰 수"를 의미합니다.

최소공배수(LMC)란?
- 두 수의 공통된 "배수 중에서 가장 작은 수"를 의미합니다.

약수(Divisors)란?
- 어떤 수를 나누어 떨어지게 하는 수를 그 수의 약수라고 합니다.
- 예를 들어 10의 약수는 1, 2, 5, 10입니다.

배수(Multiple)란?
- 배수는 어떤 수의 배를 이루는 수를 말합니다.
- 예를 들어 24는 12의 배수이며 시간의 배수는 1시간의 4배인 4시간을 말합니다.
 
C언어]

int GCD(int a, int b)

{

   int namugi = a%b;

   if(namugi == 0)

      return b;

   return GCD (b, namugi)

}

 

Python]

def GCD (a, b):

    return a if b==0 else GCD (b, a%b)

 

 

출처]

나무위키 : 유클리드 호제법

 

 

참고 문제]

C언어 195제] 2004년 한국정보올림피아드 지역본선 중등/고등부 1번 최대공약수와 최소공배수

 

 

 

 

 

※ 10월 25일은 독도의 날입니다.

대한민국의 아름다운 영토, 독도의 겨울