C++で約数の個数がN個を超える最初の三角数を求める方法

このチュートリアルでは、約数の個数がn個より多い三角数をC++で見つける方法を解説します。

三角数とは？

三角数とは、1から始まる自然数を順に足し合わせたときに得られる数のことです。例えば、1、3（1+2）、6（1+2+3）、10（1+2+3+4）といった数が該当します。つまり、ある自然数k以下の数の総和が与えられた数と一致するとき、その数は三角数であるといえます。

三角数の概要が理解できたところで、問題を解くための手順を見ていきましょう。

解き方の手順

• 基準となる数nを初期化します。

• 条件を満たす数が見つかるまでループ処理を行います。

• その数が三角数かどうかを判定します。

• その数の約数の個数がnより大きいかどうかを判定します。

• 両方の条件を満たした場合、その数を出力してループを終了します。

サンプルコード

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

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

// 三角数かどうかを判定する関数
bool isTriangular(int n) {
    if (n < 0) {
        return false;
    }
    int sum = 0;
    for (int i = 1; sum <= n; i++) {
        sum += i;
        if (sum == n) {
            return true;
        }
    }
    return false;
}

// 約数の個数を数える関数
int divisiorsCount(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int n = 2, i = 1;
    while (true) {
        // 三角数であり、かつ約数の個数がnより多いかを判定
        if (isTriangular(i) && divisiorsCount(i) > 2) {
            cout << i << endl;
            break;
        }
        i += 1;
    }
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

6

出力の解説

結果が「6」になる理由を確認してみましょう。

• 1：約数は1のみで1個 → 条件を満たさない

• 3：約数は1と3の2個 → 条件を満たさない

• 6：約数は1、2、3、6の4個 → 条件を満たす最初の三角数

このように、約数の個数が2個を超える最初の三角数は「6」になります。

計算量を改善するポイント

上記のdivisiorsCount関数はO(n)の計算量が必要ですが、約数はペア（i と n/i）で現れる性質を利用すると、O(√n)まで高速化できます。

int divisiorsCount(int n) {
    int count = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            count += (i * i == n) ? 1 : 2;
        }
    }
    return count;
}

大きな数を扱う場合は、この最適化版を使うことで処理速度を大幅に向上させることができます。

まとめ

本記事では、C++を使って約数の個数がn個を超える最初の三角数を求める方法を解説しました。「三角数の判定」と「約数のカウント」という2つの関数を組み合わせることで、シンプルに実装できることがわかりました。チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。