[알고리즘] 유클리드 호제법 - 최대공약수/최소공배수 문제

유클리드 호제법이란? (=유클리드 알고리즘)

- 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나.

- 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘.

 

원리

- 2개의 자연수 a,b에 대해서 (a>b)

a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

r을 구하는 과정을 반복하여 r이 0이 되었을 때, 나누는 수가 a와 b의 최대공약수이다.

 

java

 public static int gcd(int p, int q)
 {
	if (q == 0) return p;
	return gcd(q, p%q);
 }

 

최소공배수 구하는 공식은?

a * b / 최대공약수

 

코드 완성본

class Solution {
    public int[] solution(int n, int m) {
        int small = 0;
        int big = 0;
        
        if(n > m) {
            big = n;
            small = m;
        } else {
            big = m;
            small = n;
        }
        
        int result1 = gcd(big, small); //최대공약수
        int result2 = big * small / result1; //최소공배수
     
         int[] answer = {result1, result2};
         return answer;
    }
    public static int gcd(int x, int y){
            if(y == 0) return x;
            return gcd(y, x%y);
        }
}