C++로 자연수의 모든 약수 구하기 - 기본 편

이 튜토리얼에서는 자연수의 모든 약수를 찾는 프로그램을 작성해 보겠습니다. 비교적 간단한 문제이므로, 해결 과정을 단계별로 차근차근 살펴보겠습니다.

문제 해결 접근 방식

• 약수를 구할 자연수를 초기화합니다.

• 1부터 해당 숫자까지 반복하는 루프를 작성합니다.

  • 현재 숫자로 주어진 숫자를 나누었을 때 나머지가 0인지, 즉 나누어떨어지는지 확인합니다.

  • 나누어떨어진다면 그 숫자는 약수이므로 출력합니다.

예제 코드

그럼 바로 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void findDivisors(int n) {
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            cout << i << " ";
        }
    }
    cout << endl;
}
int main() {
    findDivisors(65);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

1 5 13 65

65의 약수는 1, 5, 13, 65로 정확하게 출력된 것을 확인할 수 있습니다.

시간 복잡도

이 방법은 1부터 n까지 모든 수를 하나씩 검사하기 때문에 시간 복잡도는 O(n)입니다. 하지만 약수는 항상 쌍(pair)으로 존재한다는 성질을 활용하면 √n까지만 검사하여 O(√n)으로 최적화할 수 있습니다. 이 최적화 방법은 다음 세트에서 자세히 다루겠습니다.

마무리

지금까지 C++로 자연수의 모든 약수를 찾는 가장 기본적인 방법을 알아보았습니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 언제든지 댓글로 남겨주세요.