C++で配列内の「割り切れるペア」の数を数える方法

本記事では、任意のサイズの整数型要素を持つ配列が与えられたとき、その中から「一方の要素がもう一方の要素を割り切れる」ようなペア（整除ペア）の総数を求める方法を解説します。

配列とは、同じ型の要素を固定サイズで連続的に格納できるデータ構造の一種です。複数のデータをまとめて管理するために使われますが、「同じ型の変数の集まり」と捉えたほうが理解しやすい場合も多いでしょう。

具体例

入力：int arr[] = {1, 2, 3, 6}
出力：count is 4

説明：(1,2)、(1,3)、(1,6)、(3,6) の4つのペアにおいて、一方の要素が他方の要素を割り切れます。1はあらゆる整数を割り切れ、さらに3は6を割り切れるためです。よって答えは4になります。

入力：int arr[] = {2, 5, 10}
出力：count is 2

説明：(2,10) と (5,10) の2つのペアにおいて、2は10を割り切れ、5も10を割り切れます。よって答えは2になります。

アルゴリズムの考え方

• 配列 arr[] を用意します。
• length() 関数（C++では sizeof 演算子など）を使い、配列の長さ＝要素数を整数値として取得します。
• 条件を満たすペアの個数を記録するカウンタ変数を用意し、0で初期化します。
• 外側のループで i を 0 から配列サイズ未満まで回します。
• 内側のループで j を i+1 から配列サイズ未満まで回し、すべてのペアを重複なく調べます。
• arr[i] % arr[j] == 0 または arr[j] % arr[i] == 0 が成立する場合はカウントを1増やします。
• ループ完了後、カウントを返します。
• 結果を出力します。

サンプルコード

#include <iostream>
using namespace std;
int divisibles(int a[], int size){
    int result = 0;
    // すべてのペアを走査する
    for (int i=0; i<size; i++){
        for (int j=i+1; j<size; j++){
            if (a[i] % a[j] == 0 || a[j] % a[i] == 0){
                result++;
            }
        }
    }
    return result;
}
int main(){
    int a[] = {1, 4, 7, 8, 9};
    int size = sizeof(a) / sizeof(a[0]);
    cout <<"count is " <<divisibles(a, size);
    return 0;
}

実行結果

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

count is 5

計算量と注意点

この手法ではすべてのペアを二重ループで確認するため、時間計算量は O(n²) となります。配列のサイズが大きくなるほど処理時間が増加する点に注意してください。また、配列に 0 が含まれている場合、剰余演算でゼロ除算が発生するため、実装の際には 0 の扱いへの配慮が必要です。