수학- 약수 , 최대공약수 , 최소공배수 (JAVA)

약수란?

어떤 수를 나누어 나머지가 없이 떨어지게 하는 수를 약수라고 한다.

만약 10을 약수로 나누면 1,2,5,10 으로 나누어 떨어진다.

 

약수 구하기 (기본적인 풀이 방법)

int num = 987654321;
long beforeTime = System.currentTimeMillis();
ArrayList result = new ArrayList<>();
for (int i = 1; i <=num / 2 ; i++) {
    if( num % i == 0){
        result.add(i);
    }
}
result.add(num); // 마지막수를 더함
long afterTime = System.currentTimeMillis();
long DiffrenceTime = afterTime - beforeTime;
System.out.println("Time : "+ DiffrenceTime);
System.out.println(result);

속도 개선 (제곱근을 활용해준 코드)

int num1 = 987654321;
long beforeTimeSqlt = System.currentTimeMillis();

// 제곱근 활용하여 약수 구하기

ArrayList sqltResult = new ArrayList<>();

for (int i = 1; i <= (int) Math.sqrt(num1) ; i++) {
    if (num1 % i == 0){
        sqltResult.add(i);
        if(num1 / i != i){
            sqltResult.add(num1 / i);
        }
    }
}
Collections.sort(sqltResult);




long afterTimeSqlt = System.currentTimeMillis();
long DiffrenceTimeSqlt = afterTimeSqlt - beforeTimeSqlt;
System.out.println("Time : " + DiffrenceTimeSqlt);
System.out.println(sqltResult);

제곱근을 활용 한다면 시간적인 면에서 더 빠르게 구현 할 수 있다.

기본적으로 알고 있는 약수 구하는 방식에서 약수의 개수를 구한다면 주어진 num 의 값을 1~num /2 까지 나누어 0일경우까지 판별해서 넣어주는 방식이라  O(n) 의 값이라 큰 값이 들어올 경우 비효율 적이다. 

 

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

 

최대 공약수는 재귀문을 이용하면 간단하게 풀 수있다.

 public int gcd (int num1, int num2 ){ // num1 = 10 , num2 = 6
        if(num1 % num2 == 0) {
            return num2;
        }
        return gcd(num2, num1%num2);
    }

step 1:

     10 % 6 == 0  False

     return gcd(6,4)

step 2:

     6 % 4 == 0 False

     return (4 , 2)

step 3: 

     4 % 2 == 0 True 

     return 2 -> 최대 공약수는 2이다.

 

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

gcd 함수를 구현해놨다면 쉽게 풀수있는 부분이다.

최소공배수의 경우 두 수를 곱하고 그 값의 최대 공약수로 나누어 주면 구할 수있다.

이것 또한 재귀함수로 풀수 있다.

public int getLCM(int numA , int numB){
        int lcm = -1;
        int gcd = this.gcd(numA , numB);
        if(gcd != -1){
            lcm = numA * numB / gcd;
        }
        return lcm;
    }

기본적인방법 두 수를 곱하고 gcd 로 나눈 값

public int lcm ( int numA , int numB){
	return (numA * numB) / gcd(numA, numB);
 }