문제 소개
이 튜토리얼에서는 주어진 범위 안에서 약수의 개수가 홀수인 숫자의 개수를 구하는 C++ 프로그램을 살펴보겠습니다.
범위의 하한(lower limit)과 상한(upper limit)이 주어지면, 해당 구간에 속한 숫자들 중 약수의 개수가 홀수인 값이 몇 개인지 계산하는 것이 우리의 과제입니다.
핵심 원리: 완전제곱수만 약수가 홀수 개다
자연수의 약수는 일반적으로 쌍을 이루기 때문에 대부분 약수의 개수는 짝수입니다. 예를 들어 12의 약수는 (1, 12), (2, 6), (3, 4)의 세 쌍으로 총 6개입니다.
하지만 완전제곱수(perfect square)는 제곱근이 정확히 가운데에 위치하므로 약수의 개수가 홀수가 됩니다.
- 1 → 약수: {1} → 1개
- 4 → 약수: {1, 2, 4} → 3개
- 9 → 약수: {1, 3, 9} → 3개
따라서 "약수의 개수가 홀수인 수"를 찾는 문제는 사실상 "범위 안의 완전제곱수의 개수"를 구하는 문제와 같습니다.
구현 예제: 브루트 포스 방식
먼저 각 숫자마다 1부터 자기 자신까지 모든 수로 나누어 약수의 개수를 직접 세는 기본적인 코드입니다.
#include <bits/stdc++.h>
using namespace std;
// 약수의 개수가 홀수인 값의 개수를 세는 함수
int OddDivCount(int a, int b) {
int res = 0;
for (int i = a; i <= b; ++i) {
int divCount = 0;
// i의 모든 약수 개수를 계산
for (int j = 1; j <= i; ++j) {
if (i % j == 0) {
++divCount;
}
}
// 약수의 개수가 홀수이면 카운트 증가
if (divCount % 2) {
++res;
}
}
return res;
}
int main() {
int a = 1, b = 10;
cout << OddDivCount(a, b) << endl;
return 0;
}
출력 결과
3
1부터 10까지의 숫자 중 약수의 개수가 홀수인 수는 1, 4, 9의 세 개이므로 결과로 3이 출력됩니다.
시간 복잡도 분석
위 코드는 각 숫자마다 1부터 n까지 반복하므로 시간 복잡도는 O((b − a + 1) × b)입니다. 범위가 커질수록 실행 속도가 크게 느려질 수 있다는 단점이 있습니다.
최적화된 접근: 제곱근 활용
완전제곱수의 성질을 이용하면 훨씬 간단하고 빠르게 해결할 수 있습니다. 각 숫자의 제곱근을 구한 뒤, 그 제곱이 원래 수와 같은지만 확인하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
int OddDivCount(int a, int b) {
int res = 0;
for (int i = a; i <= b; ++i) {
int root = (int)sqrt(i);
if (root * root == i) {
++res; // 완전제곱수라면 약수의 개수는 홀수
}
}
return res;
}
int main() {
int a = 1, b = 10;
cout << OddDivCount(a, b) << endl;
return 0;
}
이 방법은 시간 복잡도가 O(b − a + 1)로 줄어들어, 훨씬 큰 범위에서도 빠르게 동작합니다.
마무리
약수의 개수가 홀수인 수는 오직 완전제곱수뿐이라는 수학적 성질만 기억하면, 단순 반복문 방식부터 제곱근을 활용한 최적화 방식까지 다양하게 문제를 해결할 수 있습니다. 코딩 테스트에서 비슷한 유형의 문제를 만났을 때 이 성질을 떠올리면 큰 도움이 될 것입니다.