유클리드 호제법 (Euclidean algorithm), 유클리드 알고리즘과 최대공약수 & 최소공배수 구하기.

1. 유클리드 호제법과 최대 공약수 구하기.

 

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

 

호제법이란 말자체에서 알 수 있듯이 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다

 

일반적으로 최대공약수를 구하기 위해선 먼저 소인수분해를 해야한다.

 

두 수를 소인수분해한 후, 공통된 소수를 찾으면 된다. 

 

하지만!! 이 방법은 수가 커질수록 소인수분해하기 어려워진다는 단점이 있으며,

 

이때, 유클리드 호제법을 사용하면 조금 더 효율적으로 최대공약수를 구할 수 있다!!!!!!

 

방법은 아래와 같다

 

두개의 자연수 A, B (A>B) 가 있을때 큰수(A)를 작은 수(B) 로 나누면 몫(C)와 나머지(D)를 구할 수 있다.

 

A / B = C,    A%B =D

 

이때 중요한 것은 나머지이다. 

 

나머지 (D) 가  0이 아니라면 나눠준 수 (B)에 (D)를 나누어서 다시 나머지(D')을 구한다.

 

이 과정을 반복하여 나머지가 0이 되는 때의 나눠 준 수가 최대공약수가 된다.

 

예시)

 

A=115, B=35 일때

 

115 % 35 = 10

 

35 % 10 = 5

 

10 % 5 = 0

 

즉 최대 공약수는 5가 된다.

 

(%는 두 수를 나누었을 때 나머지를 구하는 기호)

 

 

2. 최소 공배수 구하기

 

최대 공약수를 구하였다면, 최소 공배수는 간단하게 구할 수 있다.

 

두개의 자연수 A, B (A>B) 가 있을때, (A x B) / 최대공약수 를 해주면 최소공배수를 구할 수 있다.

 

즉!!!  최소공배수 =  (A x B) / 최대공약수 

 

예시)

 

A=115, B=35 일때

 

최소공배수 = (115 x 35)/5 = 805 가된다.