최대 공약수, 최소 공배수 구하기

두 수 A,B의 최대공약수(GCD)를 G, 최소공배수(LCM)를 L이라고 하면, 다음 식이 성립한다.

 

AB=LG

 

최대 공약수 G = AB/L

최소 공배수 L = AB/G

 

public class Practice {
    
//  약수
    public ArrayList getDivisor(int num) {
        ArrayList result = new ArrayList();
        for (int i = 1; i <= num ; i++) {
            if (num % i==0) {
                result.add(i);
            }
        }
        return result;
    }

//  최대 공약수
//  GCD: the Greatest Common Denominator
    public int getGCD(int numA, int numB) {
        ArrayList<Integer> a = this.getDivisor(numA);
        ArrayList<Integer> b = this.getDivisor(numB);

        HashSet<Integer> setA = new HashSet<>();
        HashSet<Integer> setB = new HashSet<>();

        for (Integer nA : a) {
            setA.add(nA);
        }
        for (Integer nB : b) {
            setB.add(nB);
        }

        setA.retainAll(setB);
        int answer = setA.stream().mapToInt(x -> x).max().getAsInt();


        return answer;
    }

//  최소 공배수
//  LCM: the Lowest Common Multiple
    public int getLCM(int numA, int numB) {
        int lcm = numA * numB / this.getGCD(numA,numB);


        return lcm;
    }

    public static void main(String[] args) {

//      Test code
        int number1 = 10;
        int number2 = 6;

        Practice p = new Practice();
        ArrayList l1 = p.getDivisor(number1);   // 10: 1, 2, 5, 10
        ArrayList l2 = p.getDivisor(number2);   // 6: 1, 2, 3, 6
        System.out.println("l1 = " + l1);
        System.out.println("l2 = " + l2);

        System.out.println("최대 공약수: " + p.getGCD(number1, number2));
        System.out.println("최대 공배수: " + p.getLCM(number1, number2));
    }
}