최대 공약수, 최소 공배수 구하기 (JAVA)

두 수가 주어지며, 두수의 최대 공약수와 최소 공배수를 구하라

 

 

 

약수란?

약수란 어떤 수를 나누어떨어지게 하는 수를 말한다. 약수에는 항상 1과 자기 자신을 포함한다.

12의 약수를 구하면 1, 2, 3, 4, 6, 12 가 된다.

 

 

최대 공약수란?

0 이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수 이다. 따라서 두 정수 a, b 의 최대 공약수는 a 의 약수인 동시에 b의 약수인 수, 즉 두 정수 a, b 의 공약수 중에서 가장 큰 수를 의미한다.

 

 

최소 공배수란?

0이 아닌 두 개 이상의 정수의 양의 공배수 중에서 가장 작은 수이다. 따라서 두 정수 a, b의 최소 공배수는 a 의 배수인 동시에 b 의 배수인 수, 즉 두 정수 a, b 의 공배수 중에서 양수인 것 중 가장 작은 수를 의미한다.

-네이버 지식 백과 참고-

 

 

---

 

getDivisor

 

약수를구할때 for 문을 num 만큼 반복해도 되지만 num / 2 를 하면 불필요한 계산을 안해도 된다.

약수는 자기 자신을 2 로 나눈 수의 이상으로 나눠지지 않기 때문이다.

 

num 을 i 로 나눈 나머지가 0이 되면 i 가 num 의 약수가 되므로 ArrayList 인 result 에 add 하여 값을 추가 시킨다.

 

 

getGCD

 

최대 공약수는 두 수의 약수 중에서 공통 되면서 가장 큰 수 이다.

getDivisor 를 통해 두 수의 약수를 구한 다음 두 수를 비교해서 가장 큰 수를 찾으면 된다.

 

두 수는 getDivisor 에서 ArrayList 형태로 반환이 되기 때문에 get 으로 값을 가져 올 수 있다.

get 으로 가져온 값의 형태는 element 이므로 if 문에서 (int) 를 이용하여 형 변환 뒤 숫자를 비교하였다.

 

 

getLCM

 

최소 공배수는 두 수를 곱한 다음 최대 공약수로 나누면 쉽게 구할 수 있다.

 

 

 

import java.util.ArrayList;

public class Practice {
    
//  약수
    public ArrayList getDivisor(int num) {
        ArrayList result = new ArrayList();

        for (int i = 1; i <= num/2; i++) {
            if(num % i == 0){
                result.add(i);
            }
        }
        result.add(num);

        return result;
    }

//  최대 공약수
    public int getGCD(int numA, int numB) {
        int gcd = -1;

        ArrayList a = getDivisor(numA);
        ArrayList b = getDivisor(numB);

        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                if(a.get(i) == b.get(j)){
                    if((int)a.get(i) > gcd){
                        gcd = (int) a.get(i);
                    }
                }
            }
        }

        return gcd;
    }

//  최소 공배수
    public int getLCM(int numA, int numB) {
        int lcm = -1;

        lcm = numA * numB / this.getGCD(numA,numB);

        return lcm;
    }

    public static void main(String[] args) {

        int number1 = 10;
        int number2 = 6;

        Practice p = new Practice();
        ArrayList l1 = p.getDivisor(number1);  
        ArrayList l2 = p.getDivisor(number2);  
        System.out.println("l1 = " + l1);
        System.out.println("l2 = " + l2);

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