Algorithm 최대공약수와 최소공배수

최대공약수 최소공배수

최대공약수 최소공배수를 구하기 위한 방법

• 최대공약수는 입력받은 값의 약수중 최대값을 찾는 것임으로 먼저 입력받은 값의 약수를 먼저찾는다.
• 약수중 같은 값을 찾고 그중 가장 큰값을 answer[0]에다가 저장한다.
• 최소공배수는 입력받은 a와 b를 곱한뒤에 최대공약수로 나눈다음에 answer[1]에다가 저장한다.

import java.util.Arrays;

class TryHelloWorld {
	
    public int[] gcdlcm(int a, int b) {
        int[] answer = new int[2];
    		int[] alist = new int[a];  
      	int[] blist = new int[b];  
      	
      	answer[0] = 0;
      	for(int i = 1; i <=a; i++) {
        	if(a%i == 0 ) {
            alist[i-1] = i;
            System.out.println("alist" + alist[i-1]);
          }
        }
        for(int i = 1; i <=b; i++) {
        	if(b%i == 0 ) {
            blist[i-1] = i;
            System.out.println("blist" + blist[i-1]);
          }
        }
        
        for(int i = 0; i<alist.length; i++) {
        	Arrays.sort(blist);
        	int idx = Arrays.binarySearch(blist, alist[i]);
        	if(idx>=0) {
        		if(answer[0] <= alist[i]) {
        			answer[0] = alist[i];
        		}
        	}
        }
        answer[1] = (a*b)/answer[0];
				      
        return answer;
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        TryHelloWorld c = new TryHelloWorld();
        System.out.println(Arrays.toString(c.gcdlcm(3, 12)));
    }
}