C++で数値が「異常数（アンユージュアル・ナンバー）」かどうかを判定する方法

異常数（アンユージュアル・ナンバー）とは？

本記事では、ある数値が異常数（unusual number）であるかどうかを判定する方法を解説します。異常数とは、その数の最大の素因数が、その数自身の平方根よりも厳密に大きい数のことです。

異常数の例としては、次のような数が挙げられます。

2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 26, 28, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 46

判定の考え方

この問題を解くための手順はシンプルです。まず対象の数の最大の素因数を求め、それが元の数の平方根より大きいかどうかを確認します。大きければその数は異常数であり、そうでなければ異常数ではありません。

アルゴリズムの流れ

1. 数から2をすべて取り除き、最大素因数の候補を2に更新する
2. 3から順に奇数で試し割りし、割り切れる限り割り続けて最大素因数を更新する
3. ループ終了後に残った数が2より大きければ、それ自体が最大の素因数である
4. 求めた最大素因数と平方根を比較して判定する

C++による実装例

#include <iostream>
#include <cmath>
using namespace std;

// 最大の素因数を求める関数
int largestPrimeFactor(int num) {
    int max_prime = -1;
    while (num % 2 == 0) { // 数から2をすべて取り除く
        max_prime = 2;
        num >>= 1;
    }
    for (int i = 3; i <= sqrt(num); i += 2) {
        while (num % i == 0) {
            max_prime = i;
            num = num / i;
        }
    }
    if (num > 2)
        max_prime = num;
    return max_prime;
}

// 異常数かどうかを判定する関数
bool isUnusual(int num) {
    int largePrimeFactor = largestPrimeFactor(num);
    if (largePrimeFactor > sqrt(num)) {
        return true;
    } else {
        return false;
    }
}

int main() {
    int n = 14;
    if (isUnusual(n)) {
        cout << n << " is an unusual number";
    } else {
        cout << n << " is not an unusual number";
    }
}

実行結果

14 is an unusual number

結果の解説

例として挙げた n = 14 の場合を見てみましょう。14 は 2 × 7 と素因数分解できるため、最大の素因数は 7 です。一方、14 の平方根は約 3.74 です。最大の素因数 7 が平方根 3.74 よりも大きいため、14 は異常数であると判定されます。

このように、素因数分解によって最大の素因数を効率よく求めれば、任意の整数が異常数かどうかを簡単に判定できます。