이 튜토리얼에서는 n²(제곱)의 약수 중에서 n 자신의 약수에 해당하지 않는 수의 개수를 구하는 C++ 프로그램을 작성해 보겠습니다.
예를 들어 n이 6이라면 n²은 36입니다. 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36으로 총 9개이며, 이 중 6의 약수인 1, 2, 3, 6을 제외하면 4, 9, 12, 18, 36의 5개가 남습니다. 즉, 정답은 5가 됩니다.
문제 해결 접근 방법
문제는 매우 직관적이며, 다음 단계를 따라 해결할 수 있습니다.
숫자 n을 초기화합니다.
약수 개수를 세기 위한 카운터 변수를 초기화합니다.
2부터 n²까지 반복하면서 다음 조건을 검사합니다.
n²이 현재 숫자로 나누어 떨어지면서, 동시에 n은 현재 숫자로 나누어 떨어지지 않는다면 카운트를 1 증가시킵니다.
반복이 끝나면 최종 카운트를 반환하고 출력합니다.
C++ 코드 예제
위 로직을 그대로 구현한 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int getNumberOfDivisors(int n) {
int n_square = n * n;
int divisors_count = 0;
for (int i = 2; i <= n_square; i++) {
if (n_square % i == 0 && n % i != 0) {
divisors_count++;
}
}
return divisors_count;
}
int main() {
int n = 6;
cout << getNumberOfDivisors(n) << endl;
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
5
시간 복잡도 개선 아이디어
위 방법은 2부터 n²까지 전부 검사하므로 시간 복잡도가 O(n²)입니다. n이 커지면 비효율적일 수 있지만, 수학적 성질을 활용하면 훨씬 빠르게 계산할 수 있습니다.
n의 모든 약수는 항상 n²의 약수이기도 하므로, 원하는 답은 다음과 같이 정리됩니다.
정답 = τ(n²) − τ(n)
여기서 τ(x)는 x의 약수 개수를 의미합니다. n을 소인수분해하여 n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ 형태로 나타내면 다음 공식을 사용할 수 있습니다.
τ(n) = (a₁ + 1)(a₂ + 1)…(aₖ + 1)
τ(n²) = (2a₁ + 1)(2a₂ + 1)…(2aₖ + 1)
n = 6 = 2¹ × 3¹인 경우를 확인해 보면, τ(36) = 3 × 3 = 9이고 τ(6) = 2 × 2 = 4이므로 정답은 9 − 4 = 5로, 반복문 방식과 동일한 결과를 얻을 수 있습니다.
마무리
이번 튜토리얼에서는 n²의 약수 중 n의 약수가 아닌 수의 개수를 구하는 기본적인 방법과, 소인수분해를 활용한 효율적인 계산 방법까지 살펴보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.