최대공약수, 최소공배수 구하기
공약수 : 두 개 이상의 자연수(양의 정수) 중에서 공통된 약수
최대공약수 : 공약수 중 제일 큰 약수
서로소 : 공약수가 1뿐인 2개 이상의 자연수
최대공약수
- 소인수분해로 구하기 (서로소가 나올 때까지 소수로 계속 나눔)
- 출처 : https://mathbang.net/202
- 최대공약수는 6x2 = 12
공배수 : 2개 이상의 자연수 중에서 공통된 배수
최소공배수 : 공배수 중 제일 작은 공배수
최소공배수
- 위 사진에서 최소공배수는 6x2x5x4 = 240 이다.
소인수분해를 이용한 최대공약수, 최소공배수 구하기
// 소인수분해를 이용한 풀이
// 결과값 = 공약수들 + 서로소들
public static int[] factorization(int n, int m){
int divisor = 2;
List<Integer> facts = new ArrayList<Integer>();
int[] retData;
while(true){
if ((n % divisor == 0) && (m % divisor == 0)){
facts.add(divisor);
n /= divisor;
m /= divisor;
}
else{
if (divisor > n || divisor > m){
facts.add(n);
facts.add(m);
break;
}
divisor++;
}
}
retData = new int[facts.size()];
for(int i=0; i<facts.size(); i++){
retData[i] = facts.get(i);
}
return retData;
}
유클리드 호제법을 이용한 최대공약수, 최소공배수 구하기
- 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고하면 (단, a>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r0를 구하고 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a, b의 최대 공약수이다.
- 출처 : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
// gcd : 최대공약수
// lcm : 최소공배수
public static int[] gcdlcm(int n, int m){
int gcd;
int lcm;
gcd = gcd(n, m);
lcm = (n * m) / gcd;
return new int[] { gcd, lcm };
}
public static int gcd(int n, int m){
// 나머지가 0이면
if (m == 0){
// 나눈값 반환
return n;
}
// 나눈 수, 나머지 값
return gcd(m, n % m);
}
'0x20. 알고리즘' 카테고리의 다른 글
약수의 총 합 구하기 (0) | 2021.09.01 |
---|---|
소수 판별 (에라토스테네스의 체) (0) | 2021.08.30 |
두 점 사이의 거리 구하기 (1) | 2021.07.13 |