유클리드 호제법
유클리트 호제법을 통해 두 수의 최대공약수를 손쉽게 구할 수 있다. 우선 정의를 살펴보자. a,b 가 정수이고 a>=b 라고 하자. 그리고 a 를 b로 나눈 나머지를 r 이라고 하자. 이때 a와 b의 최대공약수를 (a, b)라고 하면 (a, b)=(b, r)이 성립한다.
정의만 봐서는 무슨 소리인지 알기 어려우니 예시를 살펴보자.
두 수 1071 과 1029의 최대공약수를 유클리드 호제법을 통해 구해보자.
- 1071을 1029로 나눈 나머지 -> 42
- 1029 를 42로 나눈 나머지 -> 21
- 42를 21로 나눈 나머지 -> 0
- (1071, 1029) = (21, 0) = 21
- 따라서 최대공약수는 21
최대공약수
이제 유클리드 호제법을 구현하여 최대공약수를 구해보자.
반복문 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
int gcd(int a,int b) // a > b
{
int r;
while(1)
{
int r = a%b;
if(r==0)
return b;
a = b;
b = r;
}
}
재귀 함수 사용
1
2
3
4
5
6
7
int gcd(int a,int b) // a > b
{
if(b==0)
return a;
else
return gcd(b, a % b);
}
최소공배수
최소공배수는 간단하다. 두 수 a, b 의 최대 공약수를 (a,b)라고 할 때 a, b의 최소공배수는 a*b/(a, b) 이다.
1
2
3
4
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
