C++で配列内の要素に最も多く割り切れる数を見つける方法

このチュートリアルでは、与えられた配列の中から、配列内の他の要素によって最も多く割り切れる数(割り切れる回数が最大となる値)を見つける方法を解説します。

アルゴリズムの手順

• 配列と、結果を格納する変数を初期化します。

• 外側のループで配列を走査します。

  • カウンター変数を初期化します。

  • 内側のループでもう一度配列を走査します。

    • 現在の要素が、比較対象の配列要素で割り切れる場合はカウンターをインクリメントします。

  • 現在のカウントがこれまでの最大値より大きければ、結果を更新します。

• 結果を出力します。

サンプルコード

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

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

int numberWithMaximumMultiples(int arr[], int n) {
    int result = -1;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] % arr[j] == 0) {
                count++;
            }
        }
        if (count > result) {
            result = count;
        }
    }
    return result;
}

int main() {
    int arr[] = {4, 24, 16, 3, 12, 28};
    cout << numberWithMaximumMultiples(arr, 6) << endl;
    return 0;
}

実行結果

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

4

出力の解説

この例では、24 が配列内の 4、24、3、12 の4つの要素で割り切れるため、最大カウントは 4 となります。

計算量について

このアルゴリズムは二重ループを使用するため、時間計算量は O(n²)、空間計算量は O(1) です。配列のサイズが大きい場合やさらなる高速化が必要な場合は、各要素の出現回数をハッシュマップで管理し、約数の個数を効率的に数える方法なども検討するとよいでしょう。

まとめ

本記事では、配列内の要素に最も多く割り切れる数(最大の割り切れる回数)を C++ で求める方法を紹介しました。シンプルな二重ループで実装できるため、初心者の方にも理解しやすい内容です。チュートリアルについてご不明な点がある場合は、コメント欄でお気軽にお知らせください。