안녕하세요. 이번엔 최대 공약수, 최소 공배수를 JAVA를 통해 구해보겠습니다.
코테나 다른 곳에서 알고리즘을 짜다보면 가끔 필요할 때가 있거나 알고 나면 다른 알고리즘 사고에 도움이 되지 않을까 싶습니다 . . ㅎㅎ
일단 최대 공약수와 최소 공배수를 간단하게 정리하면
-> 출처 나무위키
최대 공약수는 12와 18의 공통된 공약수들 중에서 가장 큰 숫자를 지칭합니다.
1. 최대공약수
public static int gcd(int m, int n){
if(m % n == 0) {
return m;
}
return gcd(n, m%n);
}- 입력으로 두 수 m,n(m>n)이 들어온다.
- n이 0이라면, m을 출력하고 알고리즘을 종료한다.
- m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
- 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고 반복한다.
이렇게 만들면 유클리도 호재법을 바탕으로 최대공약수를 구하는 것입니다. 2개의 정수로 ( m > n ) 최대 공약수를 구하는 알고리즘
2. 최대 공배수
최소공배수는 10과 12의 공배수 중 가장 작은 숫자를 지칭합니다.
(공배수 구하는 코드)
for (int i = 1; i < 100; i++) {
if ((i % 10 == 0) && (i % 12 == 0)) {
return i;
}
}1 ~ 100 까지의 숫자중 10으로 나눠도 0으로 떨어지고 12로 나눠도 0으로 떨어지는 숫자를 구하는 소스 입니다.
(최소 공배수 구하는 코드)
최소 공배수는 위에서 구한 최대 공약수를 활용하여 쉽게 구할 수 있다.
int lcm(int a, int b) {
return a*b / gcd(a,b); //최대 공약수 구하는 함수에 파라미터로 a,b 입력
}최대공약수 및 최소공배수를 구하는 알고리즘에선 보통 최대공약수를 구한 후 간단하게 최소공배수도 구하는 알고리즘을 구현한다.