유클리드의 호제법은 쉽게 말해서 최대공약수를 구하는 알고리즘이다.
A와 B의 최대공약수를 구한다면,
A=QB+R
위 식처럼 A와 B의 관계를 나타내도록한다.(A>B)
이상태에서 다시 제수(B)과 나머지(R)의 관계를 같은 형식으로 나타내보자.
B=Q'R+R'
나머지로 제수를 계속해서 나눠간다.
이렇게 반복하다보면 언젠가 제수가 딱 떨어지는 순간이 생기게된다. 생각해 보면 모든 수에대하여 성립한다.
이 때 떨어지는 순간 제수가 최대 공약수가 된다는 것이 호제법이다.
연습삼아 유클리드 호제법으로 최대공약수를 구해보자.
*제수:나누는 수
*피제수:나눔을 당하는수
*나머지:나머지
GCD(3,6)
2 = 6/3...0 나머지가 0일때 제수가 3이므로 GCD는 3
GCD(8,28)
3 = 28 / 8...4
2 = 8 / 4...0 나머지가 0일때 제수가 4이므로 GCD는 4
유클리드의 호제법은 이론적으로 소인수분해보다 쉬운 방법이라 한다.
또한 두수와 최대공약수를 알기 때문에 최소공배수 또한 구할 수 있다.
A=GCD*a, B=GCD*b (a와 b는 당연히 서로소가 된다.) 라 생각해보면 AB= (GCD^2)*a*b가 된다.
그러므로 AB/GCD = GCD*a*b 은 최소공배수가된다.
여기까지는 수학이었다면 우리는 프로그래머가 되어 이 위대한 알고리즘으로 최대공약수를 구하는 프로그램을 작성해보자. 전혀 어렵지 않다. 만약 c언어를 잘 모른다면 한번 흥미를 가져봐도 좋을 것이다. 이런 기본적인 알고리즘을 작성하다 보면 당신은 수학적지식을 다양하게 익히게되고, 덤으로 훌륭한 프로그래머가 되어있을 거니까.
암튼 호제법에대한 코드를 작성해보자.
보통 재귀의 방법을 쓰는데 다음과 같이 코딩하면 된다.
아름답지 않은가?
수학적 알고리즘을 프로그래밍언어로 표현한다는건 정말 흥미롭다.
C컴파일러를 깔고 설정하는건 정말 간단하기 때문이다. 그리고 C언어를 익혀놓으면 당신은 아티스트가 되는것이다.
언제든 요청하면 기본적인 설치는 설명해 드리겠다. 다만 학습의지는 본인의 몫이다.
그러면 당신은 그림을 그리는 것 처럼 세월이 지나갈 수록 세련된 코딩을 하고 있을 것이다.
한가지 방법을 더 살펴보자.
아래의 방법은 코딩을 최대한 줄여서 한 것이다. 원리를 알기전엔 가독성이 무척 떨어진다. 하지만, 감탄스러운 방법이다.
원리는 같다
나 또한 초짜지만 초보 프로그래머들께 당부하고 싶다. 영어공부는 새로운 기술 습득의 발판이된다.
프로그램에 관심이 있다면 꼭 영어공부도 열심히 하길 바란다.