C++로 구현하는 등가디지털 수(Equidigital Number)

등가디지털 수(Equidigital Number)는 수학적으로 특별한 성질을 가진 수로, 어떤 수의 자릿수가 그 수를 소인수분해했을 때 나타나는 소인수들의 전체 자릿수와 정확히 일치하는 수를 말합니다.

이 문제에서는 하나의 정수 n이 주어지며, 우리의 과제는 n까지의 모든 등가디지털 수를 찾아 출력하는 프로그램을 작성하는 것입니다.

문제 이해를 위한 예시

입력: n = 12

출력: 1 2 3 5 7 10 11

여기서 소수(2, 3, 5, 7, 11)는 소인수분해 결과가 자기 자신이므로 항상 등가디지털 수에 해당하며, 10 = 2 × 5처럼 소인수들의 자릿수 합이 원래 수의 자릿수와 같은 경우도 포함됩니다.

풀이 접근 방법

가장 단순한 해결 방법은 각 수의 인수를 구한 뒤, 소인수들을 나열했을 때의 전체 자릿수가 원래 수의 자릿수와 일치하는지 확인하는 것입니다.

소인수는 체(sieve) 방식을 사용하면 효율적으로 구할 수 있어 프로그램의 성능을 크게 향상시킬 수 있습니다.

알고리즘

1단계: 필요한 범위 내의 모든 소수를 미리 구합니다.
2단계: 수 n의 자릿수를 계산합니다.

3단계: 해당 수의 모든 소인수를 구하고, 소인수(및 지수) 표기의 자릿수를 셉니다.

4단계: 두 값을 서로 비교합니다.
5단계: 두 값이 같다면 해당 수를 등가디지털 수로 판정하여 반환합니다.

풀이 동작을 보여주는 프로그램

예제

#include<bits/stdc++.h>
using namespace std;
const int MAX = 10000;

vector <int> primes;

void findAllPrimes()
{
    bool marked[MAX/2 + 1] = {0};
    for (int i=1; i*i<= (MAX -1)/2; i++)
        for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1)
            marked[j] = true;
    primes.push_back(2);
    for (int i=1; i<=MAX/2; i++)
        if (marked[i] == false)
            primes.push_back(2*i + 1);
}

bool isEquidigital(int n) {

    if (n == 1)
        return true;
    int number = n;
    int digitSum = 0;
    while (number > 0)
    {
        digitSum++;
        number = number/10;
    }
    int primeDigits = 0 , expCount = 0, p;
    for (int i = 0; primes[i] <= n/2; i++) {
        while (n % primes[i] == 0) {
            p = primes[i];
            n = n/p;
            expCount++;
        }
        while (p > 0) {
            primeDigits++;
            p = p / 10;
        }
        while (expCount > 1) {
            primeDigits++;
            expCount = expCount / 10;
        }
    }
    if (n != 1)
    {
        while (n > 0)
        {
            primeDigits++;
            n = n/10;
        }
    }

    return (primeDigits == digitSum);
}

int main() {

    findAllPrimes();
    int n = 11;
    cout << "Printing Equidigital Numbers less than "<<n<<" : ";
    for (int i=1; i<n; i++)
        if (isEquidigital(i))
            cout<<i<<"\t";
    return 0;
}

출력 −

Printing Equidigital Numbers less than 11 : 1 2 3 5 7 10 11