[Algorithms] 최대공약수, 최소공배수 with 프로그래머스
최대공약수
두 개 이상의 자연수의 공통된 약수 중 가장 큰 공약수를 바로 최대공약수라고 한다.
예를 들면 12와 8의 최대공약수
12의 약수: 1, 2, 3, 4, 6, 12
8의 약수: 1, 2, 4, 8
두 수의 최대공약수는 4이다.
숫자가 3개 이상인 경우
1. 모든 수를 동시에 반드시 나눌 수 있는 수로 나눈다.
2. 더 이상 동시에 나눌 수 없으면 끝.
3. 왼쪽 공약수를 모두 곱한다.
최소공배수
두 개 이상의 자연수의 공통된 배수 중 가장 작은 값을 의미한다.
예를 들면 12와 8의 최소공배수
12의 배수: 12, 24, 36, 48,...
8의 배수: 8, 16, 24, 32, 40, 48,...
두 수의 공통된 배수는 24, 48,...
두 수의 최소공배수는 24이다.
숫자가 3개 이상인 경우
1. 서로소가 아닌 수가 2개라도 있으면 그 수들의 공약수로 나눈다.
2. 모든 몫이 서로소이면 끝.
3. 왼쪽 공약수와 아래 서로소를 모두 곱한다.
유클리드 호제법
2개 수의 최대 공약수를 구하는 알고리즘
a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 a, b의 최대공약수와 b, r의 최대공약수는 같다.
이 성질에 따라 a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r을 구한다.
나머지가 0이 될 때 나눈 수가 a, b의 최대공약수가 된다.
private static int gcd(int a, int b) {
int r = a % b;
if(r == 0) {
return b;
}
return gcd(b, r);
}
유클리드 호제법으로 최대공약수를 구한 다음, 최소공배수는 다음과 같이 구한다.
a * b / 최대공약수
12, 8의 최대공약수는 4
12, 8의 최소공배수는 12 * 8 / 4 = 24
a, b, c 여러 개를 구하려면 먼저 a, b의 최소공배수를 구하고, 구한 값과 c의 최소공배수를 구하면 됩니다.
프로그래머스 문제
1. 최대공약수와 최소공배수
class Solution {
public int[] solution(int n, int m) {
int[] answer = new int[2];
answer[0] = gcd(n, m);
answer[1] = n * m / answer[0];
return answer;
}
private static int gcd(int a, int b) {
int r = a % b;
if(r == 0) {
return b;
}
return gcd(b, r);
}
}2. N개의 최소공배수
class Solution {
public int solution(int[] arr) {
int answer = 0;
int a = arr[0];
int b = arr[1];
int g = gcd(a, b); //최대 공약수
answer = a * b / g; // 최소공배수
for (int i = 2; i < arr.length; i++) {
g = gcd(answer, arr[i]);
answer = answer * arr[i] / g;
}
return answer;
}
private static int gcd(int a, int b) {
int r = a % b;
if(r == 0) {
return b;
}
return gcd(b, r);
}
}끝.
참고자료