알고리즘(algorithm)feat.JAVA - 약수/최대공약수/최소공배수

자바(Java)의 알고리즘 중에 약수/최대공약수/최소공배수 에 대해 알아보도록 하자.

1) 약수 - 자연수 N에 대하여 자연수A로 나눴을때 나머지가 0일때, A는 N의 약수라고 정의한다.
2) 최대공약수 - 자연수 N,M의 공통된 약수 중 가장 큰 수를 최대공약수라고 정의한다.
3) 최소공배수 - 자연수 N,M의 공통된 배수 중 가장 작은 수를 최소공배수라고 정의한다. (두 수의 곱을 최대공약수로 나누면 그 값이 최소공배수가 된다.)

1. 약수

public class Practice {
	//약수 구하는 메서드
    public ArrayList getDivisor(int num) {
    	//약수를 담을 배열 선언
        ArrayList result = new ArrayList();
        
        for (int i = 1; i <= num; i++) {
        	//i는 1부터 num까지이므로, 나눴을 때, 나머지가 0일 때, result배열에 i를 추가한다
            if (num % i == 0) {
            	result.add(i);
            }
        }
        return result;
    }
    
    //최대 공약수
    public int getGCD(int numA, int numB) {
    	//최대 공약수를 담을 변수 선언
        int gcd = 1;
        
        //두 수(numA,numB)의 약수를 담을 배열 선언
        ArrayList divisorA = new ArrayList();
        ArrayList divisorB = new ArrayList();
        
        //두 수의 약수를 구하는 메서드
        for (int i = 1; i <= numA; i++) {
            if (numA % i == 0) {
                divisorA.add(i);
            }
        }
        for (int i = 1; i <= numB; i++) {
            if (numB % i == 0) {
                divisorB.add(i);
            }
        }
        //두 수의 약수 배열을 돌면서 가장 큰 값을 gcd에 저장
        for (int itemA : ArrayList<Integer>divisor) {
        	for (int itemB : ArrayList<Integer>divisorB) {
            	//itemA와 itemB가 같다면(두 수의 공약수라면)
                if (itemA == itemB) {
                	//그 수가 gcd보다 크면 그 수를 gcd에 저장한다.
                    if (itemA > gcd) {
                    	gcd = itemA
                    }
                }
            }
        }
        return gcd;
    }
    //최소 공배수
    public int getLCM(int numA, int numB) {
		//최소 공배수를 담을 변수 선언    
        int lcm = -1;
        
        //최대 공약수를 구하는 메서드 실행
        int gcd = this.getGCD(numA, numB);
        
        //최대 공약수를 구하는 메서드에서 정상적으로 최대 공약수가 구해 졌다면 두 수를 곱해서 최대 공약수로 나눠준다(최소공배수)
        if (gcd != -1) {
        	lcm = numA * numB / gcd;
        }
        return lcm;
    }
    //제대로 실행 되는지 확인을 위한 메인 클래스 구현
    public static void main(String[] args) {
    	
        int numA = 4;
        int numB = 20;
        
        Practice p = new Practice();
        //두 수의 약수를 배열에 집어 넣는다
        ArrayList Alist = p.getDivisor(numA);
        ArrayList Blist = p.getDivisor(numB);
        System.out.println("numA의 약수 : " + Alist);
       System.out.println("numB의 약수 : " + Blist);
       System.out.println("===구분선===");
       System.out.println("numA와 numB의 최대 공약수 : " + p.getGCD(numA,numB));
       System.out.println("numA와 numB의 최소 공배수 : " + p.getLCM(numA,numB));
    }
}
//결과값
numA의 약수 : [1, 2, 4]
numB의 약수 : [1, 2, 4, 5, 10, 20]
===구분선===
numA와 numB의 최대 공약수 : 4
numA와 numB의 최소 공배수 : 20