- thebaleuncoding
유클리드 호제법을 C언어 프로그램으로 만들어 볼까?
유클리드(Euclid)는 고대 그리스의 수학자입니다.
"학문에는 왕도가 없다."는 말을 한 사람으로도 유명합니다.
유클리드는 두 정수의 최대공약수를 구하는 유클리드 호제법이라는 알고리즘을 고안했습니다.
유클리드 호제법
a, b, 두 정수의 최대공약수를 G(a, b)라고 한다.
a, b, q, r (b=/=0) 네 정수에 대해
a = bq + r이면 G(a, b) = G(b, r)이 성립한다.
호제법은 두 수가 서로 상대방 수를 나누어서 결과를 얻는 알고리즘을 말합니다.
두 개의 자연수 a, b에 대해 a를 b로 나눈 나머지를 r이라고 했을 때
a와 b의 최대공약수는 b와 r의 최대공약수와 같다고 할 수 있습니다.
이 성질에 따라 b를 r로 나눈 나머지 r1을 구하고,
다시 r을 r1로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때
나누는 수가 a와 b의 최대공약수입니다.
#유클리드호제법을C언어프로그램으로만들어볼까?에 대해 더 알아보고 싶나요?
아래 링크로 이동하세요.