C++で質素数（Frugal Number）を判定する方法【サンプルコード付き】

この記事では、正の整数 N が与えられたときに、その数が質素数（Frugal Number）であるかどうかを判定するプログラムを C++ で作成する方法を解説します。

質素数とは？

質素数（FRUGAL NUMBER）とは、その数自身の桁数が、素因数分解による表現の桁数よりも厳密に大きい数のことです。

例：625 の場合

625 を素因数分解すると 5⁴ となります。

• 625 自身の桁数：3 桁
• 5⁴ の表現の桁数：2 桁

3 は 2 よりも厳密に大きいため、625 は質素数です。

最初のいくつかの質素数：125、128、243、256、343、512、625 など

問題を理解するための具体例

入力: n = 128
出力: 質素数である
説明:
128 の素因数分解は 2^7 で、その桁数は 2。
128 自身の桁数は 3。
したがって、128 は質素数です。

解法アプローチ

この問題を解く基本的な手順は以下の通りです。

1. n の素因数をすべて求める。
2. 素因数分解の表現（底と指数を含む）全体の桁数を数える。
3. 元の数 n 自身の桁数を数える。
4. 元の数の桁数が素因数分解表現の桁数より大きければ「質素数」、そうでなければ「質素数ではない」と判定する。

C++ 実装例

以下は、上記の解法を実装した C++ プログラムです。素数の列挙にはエラトステネスの篩を使用しています。

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

// エラトステネスの篩で n 未満の素数をすべて求める
vector<long int> calcPrimeNum(long int n){
    bool primeNos[n + 1];
    memset(primeNos, true, sizeof(primeNos));
    for (int i = 2; i * i <= n; i++) {
        if (primeNos[i] == true) {
            for (int j = i * 2; j <= n; j += i)
                primeNos[j] = false;
        }
    }
    vector<long int> allPrimeNumbers;
    for (int i = 2; i < n; i++)
        if (primeNos[i])
            allPrimeNumbers.push_back(i);
    return allPrimeNumbers;
}

// 数値の桁数を数える関数
int countNumDigits(long int n){
    long long int num = n;
    int digitCount = 0;
    while (num != 0) {
        num = num / 10;
        digitCount++;
    }
    return digitCount;
}

// n が質素数かどうかを判定する関数
bool isFrugalNum(long int n){
    vector<long int> primeNum = calcPrimeNum(n);
    long int num = n;
    long int factorDigitCount = 0;
    for (int i = 0; i < primeNum.size(); i++) {
        if (num % primeNum[i] == 0) {
            long int k = 0;
            while (num % primeNum[i] == 0) {
                num = num / primeNum[i];
                k++;
            }
            // 素因数の桁数に加え、指数が 1 より大きい場合は指数の桁数も加算
            if (k == 1)
                factorDigitCount += countNumDigits(primeNum[i]);
            else
                factorDigitCount += countNumDigits(primeNum[i]) + countNumDigits(k);
        }
    }
    return (countNumDigits(n) > factorDigitCount && factorDigitCount != 0);
}

int main(){
    long int n = 625;
    cout << "The number " << n << " is ";
    isFrugalNum(n) ? cout << "a Frugal number\n" : cout << "not a Frugal number\n";
    return 0;
}

実行結果

The number 625 is a Frugal number

まとめ

質素数の判定は、「素因数分解の表現の桁数」と「元の数の桁数」を比較するだけで実現できます。エラトステネスの篩で素数を事前に求めておくことで、効率よく素因数分解を行える点がポイントです。ぜひ実際にコードを動かして、さまざまな数で試してみてください。