C++でリファクタラブル数（Refactorable Number）を判定する方法

リファクタラブル数とは？

整数型の値（ここでは number とします）が与えられ、その数が「リファクタラブル数（Refactorable Number）」かどうかを判定するのが本記事の課題です。リファクタラブル数であれば「リファクタラブル数です」と出力し、そうでなければ「リファクタラブル数ではありません」と出力します。

ある数が、その約数の総数で割り切れるとき、その数はリファクタラブル数と呼ばれます。例えば、9 は約数が3つ（1、3、9）あり、9 は 3 で割り切れるため、リファクタラブル数です。

入出力のシナリオ例

入力 − int number = 9

出力 − リファクタラブル数です

説明 − 9 の約数は3つ（1、3、9）あり、9 は 3 で割り切れるため、リファクタラブル数です。

入力 − int number = 10

出力 − リファクタラブル数ではありません

説明 − 10 の約数は4つ（1、2、5、10）ありますが、10 は 4 で割り切れないため、リファクタラブル数ではありません。

プログラムで使用するアプローチ

• 整数型の変数（例：number）に入力を受け取ります。
• bool 型の関数 check_Refactorable(int number) にデータを渡します。
• 関数 check_Refactorable(int number) の内部では以下の処理を行います。
  • 整数型変数 count を 0 で宣言します。
  • i を 1 から sqrt(number) までループさせます。ループ内で number % i == 0 であるかを確認し、さらに number / i == i であれば（つまり平方数の場合）count を 1 だけ増やします。
  • それ以外の場合は、約数はペアで存在するため count に 2 を加算します。
  • 最後に number % count == 0 の結果を返します。
• 判定結果を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
bool check_Refactorable(int number){
    int count = 0;
    for (int i = 1; i <= sqrt(number); ++i){
        if(number % i==0){
            if(number / i == i){
                ++count;
            }
            else{
                count += 2;
            }
        }
    }
    return number % count == 0;
}
int main(){
    int number = 9;
    if(check_Refactorable(number) == 1){
        cout<<"リファクタラブル数です";
    }
    else{
        cout<<"リファクタラブル数ではありません";
    }
    return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

リファクタラブル数です

このアルゴリズムは、約数の探索を sqrt(number) までに限定することで計算量を O(√n) に抑えており、大きな数に対しても効率的に動作します。