C++で自然数の約数をすべて効率的に求める方法

このチュートリアルでは、自然数の約数をすべて求めるプログラムをC++で作成します。一見単純な問題ですが、効率的なアルゴリズムを知っておくと、大きな数を扱う際に大きく役立ちます。それでは、解決の手順を見ていきましょう。

アルゴリズムの流れ

• 対象となる数値を初期化します。
• 1から与えられた数の平方根（√n）まで繰り返すループを作成します。
  • 与えられた数が現在の数で割り切れるかどうかを判定します。
  • 割り切れる場合は、現在の数と「与えられた数 ÷ 現在の数」の2つを出力します。

なぜ平方根までのループでよいのか？

約数は必ずペアで存在します。例えば n = 65 の場合、「1 × 65」「5 × 13」という組み合わせになります。小さい方の約数が必ず √n 以下になることを利用すれば、大きい方の約数（n ÷ i）も同時に求められます。この方法により、計算量は O(n) から O(√n) に削減され、大きな数でも高速に処理できます。

コード例

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

#include <bits/stdc++.h>
using namespace std;
void findDivisors(int n) {
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            if (n / i == i) {
                cout << i << " ";
            }
            else {
                cout << i << " " << n / i << " ";
            }
        }
    }
    cout << endl;
}
int main() {
    findDivisors(65);
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の結果が得られます。

1 65 5 13

出力の解説

65の約数は「1, 5, 13, 65」の4つです。ループ内では i = 1 のとき「1 65」、i = 5 のとき「5 13」が出力されるため、結果は「1 65 5 13」の順に表示されます。約数を昇順に整理したい場合は、結果を一旦配列やベクターに格納してからソートするとよいでしょう。

まとめ

本チュートリアルでは、平方根を活用した効率的な約数の求め方を学びました。この手法は、素数判定や約数の個数を数える問題など、競技プログラミングや実務のさまざまな場面で応用できます。チュートリアルの内容について質問がある場合は、コメント欄でお気軽にお知らせください。