【C++】n²の約数のうち、nの約数ではないものを数える方法

このチュートリアルでは、n²（nの2乗）の約数のうち、n自体の約数ではないものの個数を求めるプログラムをC++で作成します。一見難しそうに思えますが、アルゴリズムは非常にシンプルです。解決までの手順を順番に見ていきましょう。

アルゴリズム

1. 数値 n を初期化します。
2. 約数を数えるためのカウンターを初期化します。
3. 2 から n² までの各整数について、次の条件を判定します。
   
   • n² がその数値で割り切れ、かつ n がその数値で割り切れない場合は、カウントを1つ増やします。
4. 最終的なカウントを出力します。

実装例

それでは、実際のコードを見てみましょう。

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

int getNumberOfDivisors(int n) {
    int n_square = n * n;
    int divisors_count = 0;
    for (int i = 2; i <= n_square; i++) {
        if (n_square % i == 0 && n % i != 0) {
            divisors_count++;
        }
    }
    return divisors_count;
}

int main() {
    int n = 6;
    cout << getNumberOfDivisors(n) << endl;
    return 0;
}

出力

上記のプログラムを実行すると、次の結果が表示されます。

5

結果の解説

n = 6 の場合、n² = 36 となり、その約数は「1, 2, 3, 4, 6, 9, 12, 18, 36」です。一方、n = 6 の約数は「1, 2, 3, 6」です。したがって、36 の約数のうち 6 の約数ではないものは「4, 9, 12, 18, 36」の 5 個となり、出力結果と一致します。

計算量について

この実装では 2 から n² までのすべての整数を走査するため、時間計算量は O(n²) になります。n が大きくなるほど処理に時間がかかるため、大きな数値を扱う場合は注意が必要です。

まとめ

本記事では、n² の約数のうち n の約数ではないものの個数を求める C++ プログラムを紹介しました。剰余演算（%）と条件分岐を組み合わせるだけで、誰でも簡単に実装できることがわかりました。本チュートリアルについて質問がある場合は、ぜひコメント欄でお知らせください。