문제 개요
이 문제에서는 하나의 자연수 N이 주어지며, 1부터 N까지 범위 [1, N]에 속한 모든 숫자에 대해 각각의 약수 개수를 구하는 것이 우리의 과제입니다.
문제 이해를 위한 예시
입력 : N = 7
출력 : 1 2 2 3 2 4 2
출력 결과를 숫자별로 살펴보면 다음과 같습니다.
- 1의 약수: {1} → 1개
- 2의 약수: {1, 2} → 2개
- 3의 약수: {1, 3} → 2개
- 4의 약수: {1, 2, 4} → 3개
- 5의 약수: {1, 5} → 2개
- 6의 약수: {1, 2, 3, 6} → 4개
- 7의 약수: {1, 7} → 2개
방법 1: 반복문으로 직접 세기
가장 직관적인 해결 방법은 1부터 N까지 차례대로 각 숫자를 검사하면서, 해당 숫자를 나누어 떨어지게 하는 값(약수)의 개수를 일일이 세는 것입니다.
구현 예제
#include <iostream>
using namespace std;
int countDivisor(int N){
int count = 1; // 1은 모든 수의 약수이므로 1부터 시작
for(int i = 2; i <= N; i++){
if(N % i == 0)
count++;
}
return count;
}
int main(){
int N = 8;
cout<<"[1, N] 범위의 모든 숫자의 약수 개수 : \t";
cout<<"1 "; // 1의 약수 개수
for(int i = 2; i <= N; i++){
cout<<countDivisor(i)<<" ";
}
return 0;
}
실행 결과
[1, N] 범위의 모든 숫자의 약수 개수 : 1 2 2 3 2 4 2 4
이 방법은 각 숫자마다 2부터 해당 숫자까지 반복 검사를 수행하므로 전체 시간 복잡도가 대략 O(N²)에 가깝습니다. 따라서 N이 커지면 실행 시간이 급격히 늘어난다는 단점이 있습니다.
방법 2: 배수 증가 방식 (체 기반 접근)
더 효율적인 방법은 소수 판별에 널리 쓰이는 '에라토스테네스의 체'와 유사한 아이디어를 활용하는 것입니다. 먼저 크기가 (N+1)인 배열을 만들어 모든 값을 1로 초기화합니다(모든 수는 1을 약수로 가지기 때문입니다). 이후 2부터 N까지의 각 숫자 i에 대해, i의 배수에 해당하는 배열 요소들을 1씩 증가시키면 됩니다. 이 과정이 끝나면 각 숫자가 가진 약수의 개수가 배열에 자동으로 누적됩니다.
구현 예제
#include <iostream>
using namespace std;
void countDivisors(int N){
int arr[N+1];
for(int i = 0; i <= N; i++)
arr[i] = 1; // 모든 수는 1을 약수로 가짐
for (int i = 2; i <= N; i++) {
for (int j = 1; j * i <= N; j++)
arr[i * j]++;
}
for (int i = 1; i <= N; i++)
cout<<arr[i]<<" ";
}
int main(){
int N = 8;
cout<<"[1, N] 범위의 모든 숫자의 약수 개수 : \t";
countDivisors(N);
return 0;
}
실행 결과
[1, N] 범위의 모든 숫자의 약수 개수 : 1 2 2 3 2 4 2 4
이 방식의 시간 복잡도는 조화급수의 성질에 의해 O(N log N)으로, 방법 1보다 훨씬 빠르게 동작합니다. N이 큰 입력값을 처리해야 하는 경우에는 배수 증가 방식을 사용하는 것이 바람직합니다.