C++로 특정 범위 내에서 정확히 K개의 홀수 약수를 가진 숫자 찾기

문제 개요

이 문제에서는 세 개의 정수 L, R, k가 주어집니다. 우리의 목표는 [L, R] 범위 안에서 정확히 k개의 홀수 개 약수를 가진 숫자의 개수를 구하는 것입니다.

단, 약수를 셀 때는 1과 그 수 자기 자신도 포함한다는 점에 유의해야 합니다.

예제로 문제 이해하기

입력:

a = 3, b = 10, k = 3

출력:

설명:

3부터 10 사이에서 정확히 3개의 약수를 가진 숫자는 다음과 같습니다.
4 : 약수 = 1, 2, 4
9 : 약수 = 1, 3, 9

풀이 접근 방법

이 문제를 해결하는 핵심 열쇠는 다음과 같은 수학적 성질입니다.

“약수의 개수가 홀수인 수는 반드시 완전제곱수이다.”

일반적으로 약수는 d와 n/d처럼 쌍을 이루기 때문에 약수의 총 개수는 항상 짝수입니다. 하지만 n이 완전제곱수인 경우에는 √n이 정수가 되어 자기 자신과 한 쌍을 이루게 되고, 바로 이 경우에만 약수의 개수가 홀수가 됩니다.

따라서 범위 내의 모든 숫자에 대해 약수를 일일이 세는 대신, 완전제곱수만 골라서 약수의 개수를 확인하면 됩니다. 이렇게 하면 불필요한 연산을 크게 줄여 실행 시간을 단축할 수 있습니다. 완전제곱수의 약수 개수가 k와 같다면 결과 카운트를 1 증가시키면 됩니다.

알고리즘 단계

[a, b] 범위의 각 숫자 i에 대해 완전제곱수인지 검사합니다.
완전제곱수라면 해당 수의 약수 개수를 계산합니다.
약수 개수가 k와 같으면 카운트를 1 증가시킵니다.
모든 숫자를 확인한 뒤 최종 카운트를 반환합니다.

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;

// 완전제곱수 여부를 확인하는 함수
bool isPerfectSquare(int n) {
    int s = sqrt(n);
    return (s*s == n);
}

// n의 약수 개수를 세는 함수
int countDivisors(int n) {
    int divisors = 0;
    for (int i=1; i<=sqrt(n)+1; i++) {
        if (n%i==0) {
            divisors++;
            if (n/i != i)
                divisors++;
        }
    }
    return divisors;
}

// 범위 내에서 k개의 홀수 약수를 가진 숫자의 개수를 구하는 함수
int countNumberKDivisors(int a,int b,int k) {
    int numberCount = 0;
    for (int i=a; i<=b; i++) {
        if (isPerfectSquare(i))
            if (countDivisors(i) == k)
                numberCount++;
    }
    return numberCount;
}

int main() {
    int a = 3, b = 10, k = 3;
    cout<<"The count of numbers with K odd divisors is "<<countNumberKDivisors(a, b, k);
    return 0;
}

실행 결과

The count of numbers with K odd divisors is 2

복잡도 분석

시간 복잡도: 범위 내 각 숫자에 대해 완전제곱수 여부를 O(1)에 판별하고, 완전제곱수에 대해서만 O(√n) 시간으로 약수를 세므로 전체 복잡도는 O((R − L) + (√R − √L)·√R) 수준입니다. 모든 수의 약수를 직접 세는 순진한 방법(O((R − L)·√R))보다 훨씬 효율적입니다.

공간 복잡도: O(1) — 추가적인 메모리를 사용하지 않습니다.