自然数の約数をすべて求める方法【C++で解説】

はじめに

このチュートリアルでは、自然数の約数をすべて見つけるプログラムをC++で作成します。約数とは、その数を余りなしで割り切ることができる整数のことです。これは非常にシンプルな問題なので、基本的なアルゴリズムの練習に最適です。それでは、解決の手順を見ていきましょう。

アルゴリズムの手順

• 調べたい自然数を初期化します。
• 1からその数まで順番にループ処理を行います。
  • 現在の数で対象の数が割り切れるかどうかを判定します（剰余演算 % を使用）。
  • 割り切れる場合は、その数は約数なので出力します。

この方法の計算量は O(n) であり、n が大きくなると処理時間が増加しますが、まずは最も分かりやすい素直な実装を紹介します。

サンプルコード

実際のコードを見てみましょう。

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

void findDivisors(int n) {
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    findDivisors(65);
    return 0;
}

コードの解説

関数 findDivisors では、変数 i を1から n まで増やしながら、n % i == 0（n を i で割った余りが0）という条件で約数かどうかを判定しています。条件を満たした値だけを標準出力に表示する仕組みです。

実行結果

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

1 5 13 65

65 の約数は 1、5、13、65 の4つであることが確認できます。

まとめ

今回は、C++を使って自然数の約数をすべて求めるプログラムを作成しました。シンプルなループと剰余演算だけで実装できる、非常に基礎的なアルゴリズムです。慣れてきたら、平方根まで調べることで計算量を O(√n) に抑える高速化にもぜひ挑戦してみてください。

このチュートリアルについて質問がある場合は、コメント欄でお知らせください。