C++で数値がトロイ数（Trojan Number）かどうかを判定する方法

概念

与えられた数 n がトロイ数（Trojan Number）であるかどうかを判定するのが本記事のテーマです。トロイ数とは、「強い数（Strong Number）」の性質を持ちながら、累乗数（perfect power）ではない数として定義されます。

ある数 n が強い数であるとは、n のすべての素因数 p について、p² もまた n の約数となっていることを意味します。言い換えれば、すべての素因数が少なくとも2回以上現れる数のことです。

ここで重要なのは、すべてのトロイ数は必ず強い数ですが、その逆は成り立たないという点です。つまり、強い数すべてがトロイ数というわけではなく、a^b（a、b はともに1より大きい正の整数）の形で表せないものだけがトロイ数となります。

具体例

入力

n = 72
72 は 6×6×2、すなわち (6^2)×2 と表せるため強い数ですが、累乗数ではありません。

出力

YES

入力

n = 16
16 は 2×2×2×2、すなわち 2^4 と表せるため強い数ですが、累乗数にもなっています。

出力

NO

アルゴリズムの考え方

判定は以下の手順で行います。

ステップ1： 素因数分解を行い、各素因数の出現回数を記録します。すべての素因数が2回以上出現していれば、その数は強い数であると判定できます。

ステップ2： 与えられた数が a^b の形で表せるかどうか（累乗数かどうか）を確認します。a^b の形で表せない場合、その数は累乗数ではありません。

ステップ3： 数が「強い数」であり、かつ「累乗数でない」とき、その数はトロイ数であると結論付けられます。

サンプルコード

// 数がトロイ数（Trojan Number）かどうかを
// 判定するC++プログラム
#include <bits/stdc++.h>
using namespace std;
bool isPerfectPower1(int n1){
    if (n1 == 1)
        return true;
    for (int x1 = 2; x1 <= sqrt(n1); x1++) {
        int y1 = 2;
        int p1 = pow(x1, y1);
        while (p1 <= n1 && p1 > 0) {
            if (p1 == n1)
                return true;
            y1++;
            p1 = pow(x1, y1);
        }
    }
    return false;
}
bool isStrongNumber1(int n1){
    unordered_map<int, int> count1;
    while (n1 % 2 == 0) {
        n1 = n1 / 2;
        count1[2]++;
    }
    for (int i1 = 3; i1 <= sqrt(n1); i1 += 2) {
        while (n1 % i1 == 0) {
            n1 = n1 / i1;
            count1[i1]++;
        }
    }
    if (n1 > 2)
        count1[n1]++;
    int flag1 = 0;
    for (auto b : count1) {
        if (b.second == 1) {
            flag1 = 1;
            break;
        }
    }
    if (flag1 == 1)
        return false;
    else
        return true;
}
bool isTrojan1(int n1){
    if (!isPerfectPower1(n1) && isStrongNumber1(n1))
        return true;
    else
        return false;
}
// メイン関数
int main(){
    int n1 = 72;
    if (isTrojan1(n1))
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

実行結果

YES