[Java] 약수의 개수 구하는 최적의 방법(알고리즘)

Java - 약수의 개수 구하기 (최적의 방법)

 

최근에 코딩테스트 문제를 풀다가 약수의 개수 관련해서 로직을 작성한 기억이 많다.

 

그러다 기본적인 방법 외에 조금 더 효율적으로 약수의 개수를 구하는 알고리즘을 만들 순 없을까 하며 찾아보다가 포스팅을 하게 되었다.

---

 

💡 일반적인 방법 (방법1)

 

number 의 약수의 개수를 구한다라고 했을 때 가장 일반적인 방법은 number를 1부터 number까지 나누어 나머지가 0 인경우를 판별하여 카운트해주는 방법이다.

 

int number = 123456789;

int cnt = 0;
for(int i=1; i<=number; i++) {
    if(number % i == 0) cnt++;
}

System.out.println(cnt);

구현한 코드이다. 위 방법은 number의 수가 커질수록 그만큼 반복문이 돌아야 하기 때문에 시간적으로 매우 비효율적이다.

---

 

💡 효율적인 방법 (방법2)

 

우리가 조금만 생각을 해보면 number의 약수가 1일 때 다른 약수는 number/1이 되므로 다른 하나의 약수는 number가 된다.

 

다시말해 number의 약수 중 하나가 i 라고 했을 때, 다른 약수는 number / i 가 되므로 하나의 약수를 알면 다른 하나의 존재가 보장된다.

 

그렇다면 1부터 어디까지의 약수를 구해야 number의 약수의 절반을 구할 수 있을까

 

int number = 123456789;

int cnt = 0;
for(int i=1; i * i <= number; i++) {
    if(i * i == number) cnt++;
    else if(number % i == 0) cnt+=2;
}

System.out.println(cnt);

---

 

📌 속도체크

 

위처럼 방법2로 개선했을 경우 실행시간이 O(√n)으로 단축된다.

 

 

❗️ 일반적인 방법(방법1) 시간체크

public class test {

    public static void main(String[] args) {
    	long beforeTime = System.currentTimeMillis();
        
        int number = 123456789;

        int cnt = 0;
        for(int i=1; i<=number; i++) {
            if(number % i == 0) cnt++;
        }

        System.out.println("약수의 개수 : " + cnt);

        long afterTime = System.currentTimeMillis();
        long secDiffTime = (afterTime - beforeTime);
        System.out.println("시간차이(ms) : "+secDiffTime);
    }
}

 

---

 

❗️ 효율적인 방법(방법2) 시간체크

public class test {

    public static void main(String[] args) {
    	long beforeTime = System.currentTimeMillis();
        
        int number = 123456789;

        int cnt = 0;
        for(int i=1; i * i <= number; i++) {
        	if(i * i == number) cnt++;
            else if(number % i == 0) cnt+=2;
        }

        System.out.println("약수의 개수 : " + cnt);

        long afterTime = System.currentTimeMillis();
        long secDiffTime = (afterTime - beforeTime);
        System.out.println("시간차이(ms) : "+secDiffTime);
    }
}

 

 

이처럼 시간 차이가 엄청나게 차이나게 되는 것을 볼 수 있다.

 

[방법1 실행시간] : 3.37
[방법2 실행시간] : 0.001

 

 

---

출처(참고)

https://chwan.tistory.com/entry/Java-%EC%95%BD%EC%88%98%EC%9D%98-%EA%B0%9C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0