유클리드 호제법

1.유클리드 호제법

유클리드 호제법이란 두수의 최대공약수(GCD)를 찾기 위한 알고리즘을 의미합니다,

-큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지가 0이 될때까지 작동하는 방법을 의미합니다.

 

[detail]

-두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의미합니다.

 

더욱 자세한 설명 -> /ko.wikipedia.org

 

2.최대공약수(GCD) & 최소공배수(LCM)

최대공약수(GCD)란?

-두 수의 공통된 "약수 중에서 가장 큰 수"를 의미합니다.

 

최소공배수(LMC)란?

-두 수의 공통된 "배수 중에서 가장 작은 수"를 의미합니다.

 

[detail]

약수(Divisors)란?

-어떤 수를 나누어 떨어지게 하는 수를 그 수의 약수라고 합니다.

-예를 들어 10의 약수는 1,2,5,10입니다.

 

배수(Multiple)란?

-배수는 어떤 수의 배를 이루는 수를 말합니다.

-예를 들어 24는 12의 배수이며 시간의 배수는 1시간의 4배인 4시간을 말합니다.

 

3.두 수의 최대공약수, 최소공배수 구현하기

유클리드 호제법 이용하여서 "최대공약수"를 구하는 방식입니다.

-이 방식은 큰 수를 작은 수로 나눈 나머지를 반복적으로 실행하여서 나머지가 0이 될 때까지 작동하여 

최대공약수를 구하는 방식입니다.

 

재귀 방식으로 구현

-b가 0이라면 a가 최대공약수가 되며, 그렇지 않으면 a % b의 최대공약수를 구합니다.

-이를 재귀적으로 반복하여 최대공약수를 구할 수 있습니다.

 

c언어 코드:

 

 

 

 

출처:adjh54.tistory.com