[Java] 약수의 개수를 구하는 효율적인 알고리즘 정리

📖약수 구하기 알고리즘

코딩테스트나 알고리즘 문제를 풀다 보면 약수를 구하는 문제를 자주 만나게 됩니다

하지만 큰 수의 경우 비효율적인 로직으로 인해 시간 초과에 부딪히는 경우가 다반사

이번 글을 통해 약수를 구하는 효율적인 알고리즘을 단계별로 정리해보려고 합니다!!

 

---

1️⃣일반적인 방법 (O(n))

 

가장 직관적으로 생각할 수 있는 방법은 1부터 n까지 모든 수를 확인하는 것입니다.

// 12의 약수를 구하는 예시
int count = 0;
for (int i = 1; i <= 12; i++) {
    if (12 % i == 0) {
        count++;
    }
}

결과: 12의 약수는 1, 2, 3, 4, 6, 12 총 6개

 

해당 방법은 O(n)의 시간복잡도를 가지므로, n이 커지면 커질수록 오래 걸려서 시간 초과가 발생할 수 있습니다.

---

1단계 방법의 속도를 개선해 보기 위해 먼저 한 가지 방법을 생각해 보았습니다.

2️⃣절반까지만 확인 + 자기 자신 추가 (O(n/2))

 

n/2까지만 확인하고 마지막에 자기 자신을 추가합니다.

// 12의 약수 구하기
int count = 0;
for (int i = 1; i <= 12 / 2; i++) {  // 6까지만 확인
    if (12 % i == 0) {
        count++;
    }
}
count++; // 자기 자신(12) 추가

결과: 12의 약수는 1, 2, 3, 4, 6, 12 총 6개

 

탐색할 필요가 없는 부분은 제외하여 꽤 많은 속도 개선을 보여주지만 여전히 큰 수에서는 느립니다.

---

3️⃣제곱근까지만 확인 (O(√n))

 

2단계에서도 여전히 큰 수에서는 속도가 느리기 때문에 로직 자체를 변경해 봅니다.

해결하기 위한 핵심 아이디어는 약수는 항상 쌍을 이룬다는 것입니다.

약수의 쌍 원리

12의 약수를 살펴보면:

• 1 × 12 = 12
• 2 × 6 = 12
• 3 × 4 = 12

이처럼 약수들이 쌍을 이루므로 n/2 보다도 작은 √12 = 3.46... 즉 제곱근까지만 확인 약수를 확인해 나가면 됩니다.

---

💡왜 제곱근(√n)까지만 확인하면 될까?

제곱근(√n)은 그 수를 둘로 나누는 경계선 역할을 하기 때문입니다.

 

12의 경우를 보면:

• √12 = 3.46...
• 12의 약수: 1, 2, 3, 4, 6, 12

제곱근을 기준으로 나누면:

• √12보다 작은 약수: 1, 2, 3
• √12보다 큰 약수: 4, 6, 12

또한 작은 약수와 큰 약수가 정확히 쌍을 이룬다는 점 또한 포인트!

• (1, 12)
• (2, 6)
• (3, 4)

결국 √12 이하의 약수(1, 2, 3)를 찾으면, 각각을 12로 나누어서 쌍이 되는 큰 약수들(12, 6, 4)을 자동으로 구할 수 있습니다.

시간복잡도를 O(n)에서  O(√n)으로 획기적으로 줄일 수 있는 것입니다.

 

다만 예외가 존재합니다.

---

⚠️완전제곱수의 경우 예외

 

완전제곱수의 경우는 다릅니다.
완전제곱수는 어떤 정수의 제곱으로 표현되는 수로, 약수의 개수가 항상 홀수 개입니다.

 

예를 들어 16 ( = 4² )의 경우:

• 16의 약수: 1, 2, 4, 8, 16
• 약수 쌍: (1, 16), (2, 8), (4, 4)

여기서 4 × 4 = 16처럼 같은 수끼리 곱해지는 경우가 있습니다. 이때 4는 16의 제곱근이므로 쌍을 이루지 않고 혼자 존재합니다.

 

따라서 제곱근이 존재하는 완전제곱수의 경우, 제곱근에 해당하는 약수는 자신의 쌍과 함께 두 번 카운트하지 않고 한 번만 카운트해야 합니다.

 

💡Java 코드로 적용해보기

int getDivisorCount(int n) {

    int count = 0;
    int sqrt = (int) Math.sqrt(n);
    
    for (int i = 1; i <= sqrt; i++) { // √n까지만 확인
        if (n % i == 0) { // 해당 숫자가 약수인지 먼저 판단
            count++;
            if (i*i != n) { // 약수라면 n의 제곱근인지 확인하고 (자기 자신과 쌍을 이루는 약수)
                count++; // 제곱근이 아니라면 count 증가
            }
        }
    }
    return count;
}

 

이 방법은 O(√n) 시간복잡도를 가지므로 이전 방법들보다 확실히 빠른 성능을 보여줍니다.

n = 10,000일 때:

• 1단계: 10,000번 반복
• 2단계: 5,000번 반복
• 3단계: 100번 반복 (√10,000 = 100)

 

앞으로 약수를 구하는 문제를 만나게 된다면 빠른 속도를 보장하는 해당 알고리즘을 적용해 보는 건 어떨까요?

---

💡해당 알고리즘을 적용한 문제

[프로그래머스, Java] 기사단원의 무기

[프로그래머스, Java] 소수 찾기

[프로그래머스, Java] 소수 만들기