[JAVA] 약수 구하기

알고리즘 문제에서 약수를 효율적으로 구하는 방법을 찾아보다 정리하기 위해 글 작성

 

약수 

약수는 특정 숫자를 나누어 나머지가 없도록 만드는 것을 말한다 

5를 1, 5로 나누면 나누어 떨어진다 

10을 1, 2, 5, 10로 나누면 나누어 떨어지며 해당 값들을 약수라고 한다 

 

JAVA에서 약수를 구하는 방법

 

일반적인 알고리즘

int num = 10;

for (int i=1; i<=num; i++) {
	if(num%i == 0) {
    	System.out.println(i);
    }
}

해당 방식의 경우 반복문을 통해서 해당 값을 나누어서 일일이 값을 다 찾아서 출력한다. 해당 방법의 경우 num 값이 커질때 마다 계산해야되는 범위가 커지며 런타임 시간이 길어지게 될 것이다.

 

Math의 sqrt() 메소드

sqrt 메소드는 값의 제곱근을 구한다. 해당 범위 만큼만 탐색하게 되므로 위에서 설명한 일반적인 알고리즘의 반복문에 비하면 더 효율적으로 약수를 구할 수 있게 된다.

 

제곱근으로 범위를 구하고 1 ~ limit 까지의 범위를 탐색하고 해당 범위에서 나누어 떨어지는 값을 추가하면 된다. 중복되는 값이 들어갈 수 있으므로 i 값을 나눈 몫이 같지 않은 경우에 추가한다.

int n = 36; // 약수를 찾을 숫자
int limit = (int) Math.sqrt(n); // 제곱근을 구함

for (int i = 1; i <= limit; i++) {
    if (n % i == 0) {
        // i는 n의 약수
        System.out.println("약수: " + i);
        
        // n을 i로 나눈 몫도 약수 (단, 중복 확인을 피하기 위해 i와 몫이 같지 않을 때)
        int quotient = n / i;
        if (i != quotient) {
            System.out.println("약수: " + quotient);
        }
    }
}