[programmers] 최소공배수와 최대공약수 (java) -1level
2022. 2. 14. 14:27ㆍAlgorithm/Programmers
문제 설명
문제 해결
이 문제는 유클리드 호제법을 안다면 풀기 쉽다.
public class 최대공약수와최소공배수 {
public int[] solution(int n, int m) {
// n, m 최대공약수와 최소공배수 를 구해라.
int[] answer = new int[2];
int a = Math.max(n,m); // 둘 중에 더 큰 수
int b = Math.min(n,m); // 둘 중에 더 작은 수
while(b!=0){
int r = a%b;
a = b;
b = r;
}
answer[0] = a;
answer[1] = n * m / a; // 두 수를 곱하고 최대 공약수로 나눠주면 최소공배수
return answer;
}
}
유클리드 호제법이란?
두 정수 a, b 가 있을 때 (a가 b 보다 더 크다고 가정) a를 b로 나눈 나머지를 r이라 하자.
이때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
반복문을 사용하여 r = 0 이 되면 두 정수의 최대공약수를 구할 수 있다.
최소공배수는 두 정수 a, b를 곱한 후 최대공약수로 나누어주면 구할 수 있다.
728x90
'Algorithm > Programmers' 카테고리의 다른 글
[programmers] 두 정수 사이의 합 (java) -1level (0) | 2022.02.19 |
---|---|
[programmers] 문자열 내 p와 y의 개수 (java) -1level (0) | 2022.02.18 |
[programmers] 문자열 내림차순으로 배치하기 (java) -1level (0) | 2022.02.17 |
[programmers] 소수 찾기 (java) -1level (0) | 2022.02.16 |
[programmers] 시저 암호 (java) -1level (0) | 2022.02.15 |