C++で等デジタル数を判定・列挙する方法を解説

等デジタル数（Equidigital Number）とは？

等デジタル数とは、その数自身の桁数と、素因数分解で表したときの桁数が一致するという、数学的に特別な性質を持つ数のことです。

例えば 10 を見てみましょう。10 の素因数分解は 2 × 5 であり、これを並べた「25」は 2 桁です。元の数 10 も 2 桁であるため、10 は等デジタル数に該当します。

本記事では、整数 n が与えられたときに、n 未満のすべての等デジタル数を求める C++ プログラムの作り方を解説します。

問題の例

入力: n = 12
出力: 1 2 3 5 7 10 11

代表的な数の判定例

なお、素数 p の素因数分解は p 自身であるため、すべての素数は必ず等デジタル数になります。また、1 は慣例的に等デジタル数として扱います。

解法アプローチ

最もシンプルな解決策は、対象の数に対して次の手順を実行することです。

1. その数の素因数をすべて求める。
2. 素因数（べき乗の場合は指数も含む）を並べた表現全体の桁数を数える。
3. 元の数の桁数と比較し、一致していれば等デジタル数と判定する。

素因数を高速に列挙するために、あらかじめ「ふるい法（エラトステネスの篩の変形）」で必要な範囲の素数をすべて計算しておくのがポイントです。

アルゴリズム

ステップ1: ふるい法により、探索範囲内の素数をすべて求める。
ステップ2: 判定対象の数 n の桁数を数える。

ステップ3: n のすべての素因数を求め、素因数と指数で構成される表現全体の桁数を数える。
ステップ4: 元の数の桁数と素因数分解表現の桁数を比較する。
ステップ5: 両者が一致した場合、その数を等デジタル数として返す。

C++ 実装例

以下は、上記のアルゴリズムを実装したサンプルプログラムです。

#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 = 12;
    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 12 : 1 2 3 5 7 10 11

コードのポイント

• findAllPrimes(): 奇数のみをマーク対象にすることでメモリ使用量と計算量を削減した、最適化されたふるい法を実装しています。
• isEquidigital(): まず元の数の桁数を求め、続いて各素因数の桁数を順に加算します。ある素因数で割れる回数（指数）が 1 より大きい場合は、指数部分の桁数も合計に含めます。
• ループ終了後に残った n が 1 でなければ、それ自体が残りの大きな素因数であるため、その桁数を加算してから比較を行います。