[ Programmers ] 최대공약수와 최소공배수 (Java)

ma.caron_g·2021년 6월 28일
0

Lv.1 - Programmers (완성)

목록 보기
22/74
post-thumbnail

1. Problem 📃


2. Constraint 🔗


3. Solution 🔑

최대공약수(GCD) / 최소공배수(LCM)

  1. 최대공약수는 구글에서 유클리드 호제법을 이용. (5번에 설명)
  2. 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나누면 구할 수 있다.

4. Code 💻

class Solution {
	public int gcd(int n, int m) {	
        	if(m==0) {
        		return n;
        	}
        	else {
        		return gcd(m, n % m);
                }
	}
    
	public int lcm(int n, int m) {
		if(n % m == 0) {
	        	return n;
                }
	        else {
	        	return n*m;
	        }
	}
    
    public int[] solution(int n, int m) {
    	int[] answer = new int[2];
        
        int max = n > m ? n : m;
        int min = n < m ? n : m;
        
        answer[0] = gcd(max, min);
        answer[1] = n*m / answer[0];
        
		return answer;
    }
}

5. Growth 🍄

< 최대공약수 구하는 공식 >

유클리드 호제법이란?

2개의 자연수 파라미터 a와 b (a > b)에 대해서 b!=0 이라면 a % b를 한 후 나온 나머지 값 r을 이용하여 b % r 을 계속 반복하여 나누는 수가 0이 될 때 파라미터. a값이 두 수의 최소 공배수가 된다.

public int gcd(int a, int b) {	
	if(b==0) {
        	return a;
        }
        else {
     	  	return gcd(b, a % b);
        }
}

혹은

public int gcd(int a, int b) {
	while(b != 0){
    		a = b;
            b = a % b;
    	}
        return a;
}

위와 같이 구할 수 있다.



< 최소공배수를 구하는 공식 >
두 수 a, b를 곱하여 두 수 a, b에 최대공약수를 나누어준다

public int lcm(int a, int b) {
	//위에서 구한 최대공약수를 gcdNum으로 칠게용..❤️
    int lcmNum = a * b / gcdNum;
    
    return lcmNum;
}
profile
다른 사람이 만든 것을 소비하는 활동보다, 내가 생산적인 활동을 하는 시간이 더 많도록 생활화 하자.

0개의 댓글