[TIL, 일일 회고] 2024.09.26 - 제곱근을 이용한 효율적인 약수 계산 방법

 

 

개요

알고리즘 문제를 풀 때 약수와 관련된 로직을 구현하면, 종종 효율성 테스트에서 통과하지 못하거나 비효율적인 코드를 작성했던 경험이 많습니다.

 

그래서 더 효율적인 약수 계산 방법에 대해 공부한 내용을 정리해보고자 합니다.

 

 

일반적인 방법

int number = 10;

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

System.out.println(count);

 

위 코드는 number의 약수 개수를 구하기 위해 1부터 number까지 반복문을 돌리며, 나머지가 0일 때마다 약수 카운트를 증가시키는 가장 일반적이고 간단한 방법입니다.

 

그러나 number가 커질수록 반복문이 수행해야 하는 횟수가 많아지기 때문에, 시간적으로 효율적이지 못한 코드입니다.

 

 

효율적인 방법

약수는 항상 쌍으로 존재합니다.

 

예를 들어, 12의 약수는 (1, 12), (2, 6), (3, 4)입니다. 이 특성을 이용하면, 제곱근까지만 검사하고도 모든 약수를 찾을 수 있습니다.

 

number의 약수가 i일 때, 다른 약수는 number / i가 되므로 하나의 약수를 알면 다른 하나의 약수도 쉽게 알 수 있습니다.

 

int number = 10;

int count = 0;
for (int i = 1; i * i <= number; i++) {
    if (number % i == 0) {
        if (i * i == number) {
            count++; // i가 number의 제곱근인 경우, 하나만 세어야 함
        } else {
            count += 2; // i와 number / i 두 개의 약수를 추가
        }
    }
}

System.out.println(count);

• i 는 제곱근까지만 반복합니다.
  • 예를들어 number= 16이면, 4까지만 반복합니다.
• if(number % i ==0)
  • i가 number의 약수인지 확인합니다.
• if(i * i == num)
  • i가 number의 제곱근인 경우입니다.
  • 이 경우 i 와 number / i가 같으므로 하나만 세어야 합니다.
  • 예를들어 16인 경우 4 * 4 = 16
• else
  • i가 number의 제곱근이 아닌경우 하나의 약수쌍을 한번에 추가합니다.
  • 예를들어 16인 경우 2와 8 두개의 약수를 동시에 추가합니다.

---

 

public class Main {
    public static void main(String[] args) {
        int number = 1000000;  // 테스트할 숫자

        // 일반적인 방법
        long startTime = System.nanoTime();
        int count1 = 0;
        for(int i = 1 ; i <= number ; i++){
            if(number % i == 0) count1++;
        }
        long endTime = System.nanoTime();
        double time1 = (endTime - startTime) / 1_000_000.0;  // 나노초를 밀리초로 변환
        System.out.printf("일반적인 방법 - 약수 개수: %d, 실행 시간: %.3f ms%n", count1, time1);

        // 효율적인 방법
        startTime = System.nanoTime();
        int count2 = 0;
        for (int i = 1; i * i <= number; i++) {
            if (number % i == 0) {
                if (i * i == number) {
                    count2++;
                } else {
                    count2 += 2;
                }
            }
        }
        endTime = System.nanoTime();
        double time2 = (endTime - startTime) / 1_000_000.0;  // 나노초를 밀리초로 변환
        System.out.printf("효율적인 방법 - 약수 개수: %d, 실행 시간: %.3f ms%n", count2, time2);
    }
}

 

 

실제 실행 시간을 찍어보면 위와 같이 엄청난 차이를 보이는 것을 확인할 수 있습니다. 이는 약수의 개수를 구할 숫자가 커지면 커질 수 록 더욱 큰 차이를 보일 것입니다.

 

제곱근을 활용한 이 알고리즘은 O(√n)의 시간 복잡도를 가지므로, 일반적인 방법에 비해 훨씬 빠르게 약수의 개수를 구할 수 있습니다.