이 문제에서는 세 개의 정수 L, R, k가 주어집니다. 우리의 목표는 주어진 범위 [L, R] 안에서 정확히 k개의 약수를 가지는 숫자의 개수를 구하는 것입니다. 이때 1과 숫자 자기 자신도 약수로 포함하여 계산합니다.
예제로 문제 이해하기
입력
a = 3, b = 10, k = 4
출력
2
설명
범위 3부터 10 사이에서 정확히 4개의 약수를 가지는 숫자는 다음과 같습니다. 6 : 약수 = 1, 2, 3, 6 8 : 약수 = 1, 2, 4, 8
해결 접근 방법
가장 직관적인 해결 방법은 범위 내의 모든 숫자에 대해 약수의 개수를 직접 세는 것입니다. 각 숫자마다 약수 개수를 계산한 뒤, 그 값이 k와 일치하면 결과 카운트를 1 증가시킵니다.
여기서 핵심은 약수 개수를 효율적으로 세는 것입니다. 1부터 n까지 모든 수를 확인하는 대신, 1부터 √n까지만 반복하면서 n을 나누어 떨어지게 하는 수 i를 찾으면, 짝이 되는 약수(n/i)도 동시에 얻을 수 있습니다. 단, i와 n/i가 같은 경우(완전제곱수)에는 중복 계산하지 않도록 주의해야 합니다.
구현 예제
#include<bits/stdc++.h>
using namespace std;
// n의 약수 개수를 구하는 함수
int countDivisors(int n) {
int divisors = 0;
for (int i = 1; i <= sqrt(n) + 1; i++) {
if (n % i == 0) {
divisors++; // 작은 약수 i
if (n / i != i)
divisors++; // 짝이 되는 큰 약수 n/i
}
}
return divisors;
}
// 범위 [a, b]에서 정확히 k개의 약수를 가지는 숫자 개수 세기
int countNumberKDivisors(int a, int b, int k) {
int numberCount = 0;
for (int i = a; i <= b; i++) {
if (countDivisors(i) == k)
numberCount++;
}
return numberCount;
}
int main() {
int a = 3, b = 10, k = 4;
cout << "The count of numbers with " << k << " divisors is "
<< countNumberKDivisors(a, b, k);
return 0;
}출력
The count of numbers with 4 divisors is 2
코드 설명 및 복잡도 분석
countDivisors 함수는 √n까지만 검사하여 약수를 쌍(i, n/i)으로 묶어 세는 방식을 사용하므로, 하나의 숫자에 대한 약수 개수를 O(√n) 시간 안에 구할 수 있습니다.
countNumberKDivisors 함수는 범위 [a, b]의 각 숫자에 대해 위 함수를 호출하여 조건을 만족하는지 확인합니다. 따라서 전체 시간 복잡도는 O((R − L + 1) × √R)이 됩니다.
참고로, 정확히 2개의 약수를 가지는 숫자는 소수(prime number)뿐이며, 정확히 3개의 약수를 가지는 숫자는 소수의 제곱수(예: 4, 9, 25)라는 성질을 활용하면 특정 k값에 대해 더 최적화된 풀이도 가능합니다.