최대 공약수와 유클리드 호제법 그리고 최소공배수
개념
최대공약수(Greatest Common Divisor, GCD)
공약수(common divisor)란 두 수 이상의 여러 수의 공통된 약수를 의미한다.
최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킨다.
소인수분해를 이용한 방법
나눗셈을 이용한 방법
유클리드 호제법
개념
유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.
호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r(a%b)의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.
ex)
a % b = r
b % r = r'
r % r' = r''
...
x % y = 0
예시
소스코드
두 가지 방법으로 최대공약수를 구하기.
1. while문
2. 재귀 함수
1. while문 이용
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
num1 = int(input("1보다 큰 정수 입력:"))
num2 = int(input("1보다 큰 정수 입력:"))
x = num1
y = num2
while y > 0:
temp = y
y = x % y
x = temp
print("{}와 {}의 최대공약수 : {}".format(num1, num2, x)) # 최대공약수
for i in range(1, x+1):
if x % i == 0:
print("{}와 {}의 공약수 : {}".format(num1, num2, i)) # 최대공약수
|
cs |
2. 재귀 함수
|
1
2
3
4
5
6
7
8
9
10
11
12
|
static int gcd(int a, int b){
if(a % b == 0){
return b;
}
return gcd(b, a % b);
}
public static void main(String[] args) {
// Test code
System.out.println(gcd(8, 32)); // 8
}
|
cs |
최소공배수 구하기
최소공배수는 최대공약수와는 반대로, 두 정수가 공통적으로 가지는 배수 중 가장 작은 값을 의미합니다.
최소공배수는 최대공약수와 밀접한 관계가 있는데, 정수 a, b의 최대공약수 G = gcd(a, b)에 대하여 아래의 식을 만족하는 정수 x와 y가 존재합니다.
a = Gx, b = Gy (단, x, y는 정수)
이 때 a * b = GGx*y 임을 알 수 있고, G는 두 수의 최대 공약수이며 x와 y는 서로소인 관계를 가집니다.
집합적으로 생각하면, a와 b의 합집합은 G, x, y이고 이 세 수를 곱한 Gxy가 최소공배수가 됨을 알 수 있습니다.
- a * b = GGx*y
- a * b / G = GGx*y / G (양변에 최소 공약수를 나누어 줌)
- a * b / G = Gxy(최소공배수)
- 최소공배수 = a * b / G
그러므로 두 수의 최소공배수 L = lcm(a, b)은 L= lcm(a, b)= a * b / gcd(a, b)이 성립합니다.
최대공약수와 최소공약수 사이의 관계와 유클리드 호제법을 활용해 구할 수도 있습니다.