최대공약수란?
A와 B의 공약수 중 가장 큰 수이다. 여기서 공약수란 A의 약수와 B의 약수 중 겹치는 수이다.
예를 들어, 6과 24를 보면 6의 약수는 1,2,3,6이고 24의 약수는 1,2,3,4,6,8,12,24 이다.
즉 공약수는 1,2,3,6이다. 여기서 가장 큰 6이 6과 24의 최대공약수가 된다.
이떄, 24를 6으로 나누면 나머지가 0이다.
A와 B의 최대공약수를 구하려고 할 떄, A % B = 0 이라면 B가 A, B의 최대공약수가 된다.
유클리드 호제법이란?
자연수 A, B의 최대공약수를 구하는 알고리즘이다.
A % B = R이라고 해보자. 만약 이때 R이 0이라면 B가 최대공약수일 것이다. 0이 아니라면
B % R = R2라고 해보자. 만약 이때 R2가 0이라면 R이 최대공약수일 것이다. 0이 아니라면
R % R2 = R3라고 해보자. 앞 과정을 나머지가 0이 될 때까지 계속 반복해서 최대공약수를 구한다.
예를 들어, 48과 36의 최대공약수를 유클리드 호제법을 이용해서 구해보자.
48 % 36 = 12. 나머지가 0이 아니므로 36과 12의 나머지를 구한다.
36 % 12 = 0. 나머지가 0이다. 즉 48과 36의 최대공약수는 12가 된다.
예를 들어, 16과 10의 최대공약수를 유클리드 호제법을 이용해서 구해보자.
16 % 10 = 6이다. 나머지가 0이 아니므로 10과 6의 나머지를 구한다.
10 % 6 = 4. 나머지가 0이 아니므로 6과 4의 나머지를 구한다.
6 % 4 = 2. 나머지가 0이 아니므로 4와 2의 나머지를 구한다.
4 % 2 = 0. 나머지가 0이다. 2가 최대공약수가 된다.
위의 알고리즘을 코드로 바꿔보자.
public static int gcd(int a, int b){
while(b!=0){
int r = a % b;
a = b;
b = r;
}
return a;
}앞에서는 a와 b를 나누고, b와 r을 나누고, r과 r2를 나눴다. 즉 a와 b를 나눈 나머지인 r을 구하고 a 자리에 b를, b 자리에 r을 넣어서 다음에는 b % r이 될 수 있도록 한다. while문에서 b가 0인지 0이 아닌지 확인하는 이유도 while문 안에서 조건을 확인하기 전, b자리에 r을 넣었기 때문이다. 만약 b가 0이라면(나머지가 0), a에 b가, b에는 r이 들어있는 상황이기 때문에 원래대로라면 b를 출력해야 맞지만, 현재 b의 값을 가지고 있는 a를 출력해야한다.
최소공배수란?
A와 B의 공배수 중 가장 작은 수이다. 여기서 공배수란 A의 배수와 B의 배수 중 겹치는 수이다.
예를 들어, 48과 36를 보면 48의 배수는 48, 96, 144, 192, 240..이고 36의 배수는 36, 72, 108, 144, .. 이다.
즉 최소공배수는 144이다.
최대공약수와 최소공배수와의 관계
유클리드 호제법에 쓰였던 예시인 48, 36으로 최대공약수와 최소공배수의 관계를 생각해보자.
48과 36의 최소공배수는 144이고, 최대공약수는 12이다.
그럼 144가 48과 36의 최대공약수인 12와 어떤 관계가 있을까?
12는 최대공약수이기 때문에 48과 36의 약수 중 하나이다. 즉 12에 어떤 수를 곱하면 48이 나오고, 12에 어떤 수를 곱하면 36이 나온다. 이때 12 * x = 48, 12 * y = 36이라고 생각해보면, x와 y는 서로소이며 x * y = 최대공약수이다.
또한 48 * 36 = 12 * 12 * x * y 이다. 이때 양변에 최대공약수를 나눠주면, (48 * 36) / 12 = 12 * 12 이고 , 12 * 12는 144 즉 최소공배수이다. 따라서 A * B / 최대공약수 = 최소공배수 이다.
위의 유클리드 호제법으로 최대공약수를 먼저 구한뒤, 구한 최대공약수를 이용해 최소공배수를 구할 수 있다.