알고리즘
[Programmers]최대공약수와 최소공배수(난이도:★★★★)
BaekGyuHyeon
2022. 5. 16. 20:39
https://programmers.co.kr/learn/courses/30/lessons/12940
코딩테스트 연습 - 최대공약수와 최소공배수
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의
programmers.co.kr
class Solution {
public int[] solution(int n, int m) {
int[] answer = {};
// 둘다 소수면 최대공약수는 1, 최소공배수는 두 수를 곱한 숫자이다.
if(isPrime(n) && isPrime(m)){
return new int[]{1,n*m};
}else{
int maxFactor = getMaxFactor(n,m);
return new int[]{maxFactor,getMinMultiple(n,m,maxFactor)};
}
}
// 최대공약수 구하기
// 두 수를 곱한 후 최대공약수로 나누면 최소공배수가 된다.
public int getMaxFactor(int n,int m){
int res = 1;
for(int i = 2; i <= Math.min(n,m); i++){
if(n % i == 0 && m % i ==0)
res = i;
}
return res;
}
// 최소 공배수 구하기
public int getMinMultiple(int n, int m,int maxFactor){
return n * m / maxFactor;
}
// 소수 판별
public boolean isPrime(int n){
for(int i = 2 ; i < n;i++){
if(n % i == 0)
return false;
}
return true;
}
}