자료구조 & 알고리즘

[기초수학/JAVA] 약수, 최대공약수, 최소공배수 알고리즘

HSRyuuu 2023. 5. 18. 20:11

초등학교? 중학교? 때 배운 수학

약수는 어떤 수를 나누었을 때 나누어 떨어지는  수들의 집합이다.

예를들어 12의 약수는 [1, 2, 3, 4, 6, 12]이다.

 

최대공약수는 두 수가 공통으로 갖는 약수 중 가장 큰 수이다.

예를들어 36과 48의 최대공약수는 12이다.

 

최소공배수는 두 수의 배수들 중 가장 작은 수이다.

예를들어 24과 36의 최소공배수는 72이다.

약수

약수 : Divisor

어떤 수 A의 약수 집합은 1과 A를 포함한다. 또한, 약수 중 A를 제외한 가장 큰 수는 A/2 보다 클 수  없다.

따라서 for문의 반복 범위는 1부터 A/2 까지로 한다.

//약수
    static List<Integer> getDivisor(int num){
        List<Integer> result = new ArrayList<>();
        for(int i=1;i<=(int)num/2;i++){
            if(num%i == 0){
                result.add(i);
            }
        }
        result.add(num);
        return result;
    }

최대공약수

최대공약수( GCD : the Greatest Common Denominator )

두 수 num1과 num2가 있을 때, num1과 num2의 약수 집합이 공통으로 갖는 수 중 가장 큰  수가 최대공약수이다.

따라서 num1과 num2의 모든 약수 집합을 돌면서 같은 수가 나올때마다 gcd값과 비교하여 더 클경우 갱신해준다. 

 

약수는 나누어떨어지는 수이다. 따라서 두 수를 동시에 같은수로 나눠가면서 '공약수' 중에서 max 값을 갱신해 간다.

public int getGCD(int num1, int num2) {
        int max =0;
        for(int i=1;i<=num1 && i<=num2;i++){
            if(num1%i==0 && num2%i==0){
                max = i;
            }
        }        
        return max;
}

약수를 이용해서 구하기

더보기 
//최대공약수
static int getGCD(int num1, int num2){
        int gcd = -1;
        List<Integer> divisor1 = getDivisor(num1);
        List<Integer> divisor2 = getDivisor(num2);
        for (Integer i1 : divisor1) {
            for (Integer i2 : divisor2) {
                if(i1 == i2 && gcd<i1){
                    gcd = i1;
                }
            }
        }
        return gcd;
    }

최대공약수 재귀함수로 구하기

더보기 
public int gcd(int a, int b){
    if(a%b == 0){
        return b;
    }
    return gcd(b,a%b);
}

a = 8, b =12 일때

  1. 8%12 !=0  => gcd(12,8)
  2. 12%8 != 0 => gcd(8,4)
  3. 8%4 == 0 => return b;

 

최소공배수

최소공배수( LCM : the Lowest Common Multiple )

최소공배수는 수학적으로 구하는 공식이 따로 있다.

num1과 num2, 두수의 최대공약수 gcd가 있을 때, 두 수의 최소공배수는 (num1 x num2) / gcd 이다.

그 이유는 소인수 분해를 해보면 알 수 있다.

24과 36를 각각 소인수 분해 해보자.

24 = 2 x 2 x 2 x 3

36 = 2 x 2 x 3 x 3

두 수의 최대공약수는 위의 소인수분해 한 경과의 인수들 중 최대한 많이 겹치면 된다.

따라서 최대공약수는 2 x 2 x 3 = 12 이다.

이때, 두 수를 각각 최대공약수 x A 로 나타낼 수 있다.

24 = 12 x 2

36 = 12 x 3

그럼 두 수의 최소공배수는 12 x 2 x 3 = 72 가 될것이다.

다시 말하면 두 수 num1, num2 중 num1 x (num2/gcd) 와 같아진다.

따라서 두 수의 최소공배수는 (num1 x num2) / gcd 가 성립한다.

 

기억해 두었다가 최소공배수를 구하는 문제를 해결할때 꼭 이용하자.

//최소공배수
static int getLCM(int num1, int num2){
        int gcd = getGCD(num1,num2);
        return (num1*num2)/gcd;
    }
반응형