C++で数値がアキレス数かどうかを判定する方法

アキレス数とは

正の整数 n が与えられたとき、その n がアキレス数であるかどうかを判定するのが本記事の課題です。n がアキレス数であれば「YES」を、そうでなければ「NO」を出力します。

数学におけるアキレス数とは、累乗数（パワフルナンバー）でありながら、完全べき乗数ではない数として定義されます。

• 累乗数：ある数 N のすべての素因数 p について、p² もまた N を割り切るような数のことです。
• 完全べき乗数：m^k（m ≥ 1、k ≥ 2）の形で表せる数のことです。

アキレス数の最初の例は以下の通りです。

72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125

入出力例

入力： 108
出力： YES
108 は 6 と 36 の両方で割り切れるため累乗数であり、かつ完全べき乗数ではないため、アキレス数です。

入力： 64
出力： NO
説明： 64 は累乗数ではありますが、2⁶ と表せる完全べき乗数でもあるため、アキレス数ではありません。

判定のアプローチ

• まず、与えられた数 N が累乗数であるかどうかを確認します。
• 次に、N が完全べき乗数であるかどうかを確認します。
• N が累乗数であり、かつ完全べき乗数でない場合、N はアキレス数です。それ以外の場合はアキレス数ではありません。

C++による実装例

// CPP program to check Primorial Prime
#include <bits/stdc++.h>
using namespace std;
bool isPowerful1(int n1){
    while (n1 % 2 == 0) {
        int power1 = 0;
        while (n1 % 2 == 0) {
            n1 /= 2;
            power1++;
        }
        if (power1 == 1)
            return false;
    }
    for (int factor1 = 3; factor1 <= sqrt(n1); factor1 += 2) {
        int power1 = 0;
        while (n1 % factor1 == 0) {
            n1 = n1 / factor1;
            power1++;
        }
        if (power1 == 1)
            return false;
    }
    return (n1 == 1);
}
bool isPower1(int a1){
    if (a1 == 1)
        return true;
    for (int i1 = 2; i1 * i1 <= a1; i1++) {
        double val1 = log(a1) / log(i1);
        if ((val1 - (int)val1) < 0.00000001)
            return true;
    }
    return false;
}
bool isAchillesNumber1(int n1){
    if (isPowerful1(n1) && !isPower1(n1))
        return true;
    else
        return false;
}
// Driver Program
int main(){
    int n1 = 108;
    if (isAchillesNumber1(n1))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    n1 = 35;
    if (isAchillesNumber1(n1))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

実行結果

YES
NO

コードの解説

isPowerful1 関数： 数を素因数分解し、各素因数の出現回数（指数）がすべて 2 以上であるかを確認することで、累乗数かどうかを判定します。指数が 1 の素因数がひとつでも存在すれば、その数は累乗数ではありません。

isPower1 関数： 2 から √a までの各整数 i について、log(a) / log(i) がほぼ整数になるかを確認します。整数になれば、その数は i のべき乗、すなわち完全べき乗数です。

isAchillesNumber1 関数： 上記の2つの関数を組み合わせ、「累乗数である」かつ「完全べき乗数ではない」という条件を満たす場合に true を返します。