최대공약수, 최소공배수 구하기 - JAVA
프로그래머스 'N개의 최소공배수' 문제풀이 후 최대공약수와 최소공배수 알고리즘을 리마인드 할 겸 정리해보았다.
최대공약수
예시
18와 48의 최대공약수는 6이다.
풀이
// 최대공약수 구하기
public int gcd(int a, int b) {
if (a == 0) {
return b;
}
return gcd(b%a, a);
}
두 숫자의 나머지 연산를 재귀적으로 수행하면 최대공약수를 구할 수 있다. (유클리드 알고리즘)
ex)
18 48
12 18
6 12
0 6
최소공배수
최소공배수를 구하기 위해 직접 계산을 하다보면 최대공약수가 필요하다는 것을 알 수 있고
이어서 최소공배수를 구하는 공식도 알게된다.
예시
18과 48의 최소공배수는 144이다.
풀이
// 최소공배수 구하기
public int lcm(int a, int b) {
return a * b / gcd(a,b);
}
// 최대공약수 구하기
public int gcd(int a, int b) {
if (a == 0) {
return b;
}
return gcd(b%a, a);
}
공식 : a * b / gcd(a,b)
Author And Source
이 문제에 관하여(최대공약수, 최소공배수 구하기 - JAVA), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hsw1606/최대공약수-최소공배수-구하기-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)