최대공약수와 최소공배수

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int end = n>m? n:m;
        for(int i=1;i<=end;i++)
        {
            if(n%i == 0 && m%i == 0)
            {
                answer[0] = i;
            }
        }
        answer[1] = n*m / answer[0];
        return answer;
    }
}

 

최소공배수 = a*b/최대공약수

최대공약수는 나눠떨어지는수

 

유클리드 호제법

1. 주어진 a,b중 큰수를 작은수로 나눈다

2. 작은수랑 나머지를 나눠준다. 나머지가 0이될때까지 나눠주고 나머지가 0이면 나누는수가 최대공약수가 된다.

즉 max값이 min이되고 min값은 나머지 값이 되면 작은수랑 나머지를 나눠주는 격이된다.

1512 /1008 ..........1 504

1008/504 .............2  0

 

class Solution {
    static public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int max = n>m? n:m;
        int min = n<m? n:m;
        int remain=0;
        int mok=0;
        while(true)
        {
            remain = max%min;
            if(remain!=0)
            {
                System.out.println(remain);
                max = min;
                min = remain;
            }
            else
            {
                if(remain==0)
                {
                    answer[0] = min;
                    break;
                }
            }
        }
        answer[1] = n*m /answer[0];
        return answer;
    }
}