유클리드 호제법 정리

유클리드 호제법을 한번 알아보았다.

LCM(least common multiple) - 최소 공배수

GCD(Greatest common divisor) - 최대 공약수

주로 LCM과 GCD 문제에서 자주 사용되는데, 그 원리를 알아본다면,

정수의 최대 공약수는 두 수의 공약수 중 가장 큰 수이다.

예를 들어 20과 8 의 최대 공약수는

20의 약수 : 1,2,4,5,10,20

8의 공약 : 1,2,4,8

20과 8의 공약수 : 1,2,4

이중 최대 공약수는 4 이다.

유클리드 호제법에 의하면

20 = 8 * 2 + 4 로 표현 가능하고 20과 8의 공약수는 8과 4의 공약수와 같다고 할 수 있다.

그렇다면 8과 4의 최대 공약수를 구한다면

8 = 4 * 1 + 4

8과 4의 공약수는 4와 4의 공약수와 같다.

결국 20과 8의 최대공약수는 4가 되는 것이다.

그렇다면 최소공배수를 알아보자.

두 수의 최소공배수는 각각의 수의 곱에 대하여 처음으로 공통된 숫자를 찾는것이다.

20과 8을 다시 예로 든다면

20의 배수 = 20,40,60,80...

8의 배수 = 8,16,24,32,40..

20과 8의 최소 공배수  = 40이 된다.

이 또한 잘 생각해보면 처음 수인 20 * 8 의 값에 서로 공통된 약수의 최대값인 최대공약수를 나눠보면 최소공배수가 나온다는 것을 알 수 있다.

20 * 8 = 160 -> 160 / 4 = 40

그럼 이를 코딩에 적용 해본다면...

#include<iostream> using namespace std; int LCM, GCD;//최소공배수,최대공약수 void lcm(int x, int y){ LCM = (x*y) / GCD; } void gcd(int x, int y){//최대 공약수 if (x%y == 0){ GCD = y; return; } gcd(y, x%y); } int main(){ int x, y; cin >> x >> y; if (x < y){ swap(x, y); } gcd(x, y); lcm(x, y); cout << GCD << endl << LCM<<endl; return 0; } 문제: 두 수의 최대공약수와 최소 공배수를 출력하시오 입력: 두개의 정수 출력: 최대공약수 최소공배수 (주석을 많이 달아놓지 않아서 이해가 힘들지도 모르지만 gcd 재귀함수를 잘 생각해보면 이해가 될것이다.)

참고 사이트 :http://blog.naver.com/taeho310/70136047251 , http://183.106.113.109/30stair/eu/eu.php?pname=eu