[알고리즘] 최대공약수, 최소공배수
최대공약수, 최소공배수를 구하는 방법을 알아보자
최대공약수(GCD)
두 자연수의 공통된 약수 중 가장 큰 수
최소공배수(LCM)
두 자연수의 공통된 배수 중 가장 작은 수
최대공약수
방법1
2부터 min(a, b) 수를 차례로 넣어 확인 -> O(n)
방법2: 유클리드 호제법
GCD(a, b) == GCD(b, a % b)
이 성질을 이용해 a % b == 0이 나올때 까지 반복. 나머지가 0이 되었을 때 나누는 수가 a, b의 최대공약수
코드
int GCD(int a, int b) {
int remainder = a % b;
if (remainder == 0) return b;
else return GCD(b, remainder);
}
최소공배수
즉, LCM(a, b) = a * b / GCD(a, b)
코드
int LCM(int a, int b) {
return a * b / GCD(a, b);
}
Author And Source
이 문제에 관하여([알고리즘] 최대공약수, 최소공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cchloe2311/최대공약수-최소공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)