C++로 자연수의 모든 약수 구하기 - 제곱근 활용 효율적 방법

이번 튜토리얼에서는 자연수의 모든 약수를 찾는 프로그램을 C++로 작성해 보겠습니다. 단순히 1부터 n까지 모두 나누어 확인하는 대신, 제곱근(√n)까지만 반복하는 효율적인 방법을 사용하면 시간 복잡도를 O(n)에서 O(√n)으로 크게 줄일 수 있습니다.

해결 접근 방식

약수는 항상 쌍(pair)으로 존재한다는 점이 핵심입니다. 예를 들어 n = 65라면, 5가 약수이면 65 ÷ 5 = 13 역시 약수입니다. 따라서 다음과 같은 순서로 문제를 해결할 수 있습니다.

• 자연수 n을 초기화합니다.

• 1부터 n의 제곱근까지 반복하는 루프를 작성합니다.

  • 현재 숫자 i가 n을 나누어 떨어뜨리는지(나머지가 0인지) 확인합니다.

  • 나누어 떨어진다면 i와 n / i 두 값을 모두 출력합니다. 이때 i == n / i인 경우(완전제곱수)에는 중복 출력을 피하기 위해 한 번만 출력합니다.

예제 코드

위 알고리즘을 그대로 코드로 옮기면 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

void findDivisors(int n) {
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            if (n / i == i) {
                // 완전제곱수인 경우 중복 출력 방지
                cout << i << " ";
            }
            else {
                cout << i << " " << n / i << " ";
            }
        }
    }
    cout << endl;
}

int main() {
    findDivisors(65);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

1 65 5 13

출력 결과를 보면 1, 65, 5, 13이 모두 65의 약수임을 알 수 있습니다. 루프가 √65 ≈ 8.06까지만 돌았음에도 네 개의 약수를 모두 찾아낸 것입니다.

시간 복잡도 분석

단순하게 1부터 n까지 전부 검사하는 방법은 O(n)의 시간이 걸리지만, 위 방법은 제곱근까지만 확인하므로 O(√n)에 완료됩니다. 예를 들어 n이 10억이라면 약 31,623번의 반복만으로 충분합니다. 큰 수의 약수를 자주 계산해야 하는 상황에서 매우 유용한 최적화 기법입니다.

마무리

이번 글에서는 제곱근을 활용해 자연수의 모든 약수를 효율적으로 찾는 C++ 프로그램을 살펴보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.