[Java] 약수의 개수 구하기

N의 약수의 개수를 구하는 방법은 일반적으로 N을 1부터 N까지의 숫자로 나누면서 약수의 여부를 카운트해주는 것이다.

코드로 구현하면 아래와 같다.

방법 (1)

int num = 123456789;

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

그러나 이 방법은 1부터 N까지 전부 검증을 해야 하기 때문에 실행시간이 O(n)으로, N값이 커질 수록 굉장히 비효율적이다.

방법 (2)

num의 약수 가운데 하나가 m이라고 했을 때, 다른 약수는 N/m이 되므로 하나의 약수를 알면 다른 하나의 존재가 보장된다.
그럼 1부터 어디까지 약수를 구해야 N의 약수의 절반을 구할 수 있을까?

아래 그림과 같이, √N까지 구하면 약수 절반의 개수를 구할 수 있다는 걸 알 수 있다.

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;
}

실행속도 비교

방법(1) 대비 방법(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 % 1 == 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 % 1 == 0) cnt+=2;
		}
        
        System.out.println("약수의 개수 : " + cnt);
        
        long aftertime = System.currentTimeMillis();
        long secDiffTime = (afterTime - beforeTime);
        System.out.println("시간차이(ms) : " + secDiffTime);
   }
}

참고: 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