C++で別の配列のいずれかの要素で割り切れる要素を数える方法

2つの整数型配列、例えば arr_1[] と arr_2[] が与えられたとき、arr_1[] の要素の中で「少なくとも1つの約数が arr_2[] に含まれる」要素の個数を求めるのがこの記事の課題です。つまり、第2配列 arr_2[] の中に約数が1つでも存在する要素だけをカウントする必要があります。

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

具体例

入力 − int arr_1[] = {1, 2, 3, 4, 5}
      arr_2[] = {2, 6, 12, 15}
出力 − カウントは 2

説明 − arr_1[] には5つの要素、arr_2[] には4つの要素があります。このうち約数が arr_2[] に存在するのは「2」と「4」の2つだけです（2の約数に2が含まれ、4の約数にも2が含まれるため）。したがってカウントは2となります。

入力 − int arr_1[] = {1, 2, 3, 4, 5}
      arr_2[] = {13, 11}
出力 − カウントは 0

説明 − arr_1[] のどの要素も、その約数が arr_2[]（{13, 11}）の中に存在しないため、カウントは0となります。

プログラムで使用するアプローチ

• 2つの配列 arr_1[] と arr_2[] を作成します。
• sizeof を使って両方の配列の長さ（要素数）を計算します。
• 該当要素の個数を保存するための一時変数を用意します。
• unordered_set 型の変数（例えば us）を作成し、検索を高速化できるようにします。
• i を 0 から第2配列のサイズ未満までループさせます。
• ループ内で arr_2[i] をセットに挿入します。
• 続いて i を 0 から第1配列のサイズ未満までループさせます。
• その内部で、j を 1 から j * j <= arr_1[i] を満たす範囲でループさせます。
• arr_1[i] % j == 0 の場合、us.find(j) != us.end() または us.find(arr_1[i] / j) != us.end() であるかを確認し、真であればカウントを1増やしてループを抜けます。
• すべての要素について判定が終わったら、カウントを返します。
• 結果を出力します。

サンプルコード

#include <iostream>
#include <unordered_set>
using namespace std;
// 第1配列のうち、少なくとも1つの約数が
// 第2配列に存在する要素の数を数える関数
int totalelements(int arr_1[], int size1, int arr_2[], int size2){
    // 要素の個数を数えるための変数 'result'
    int result = 0;
    // 第2配列の要素をハッシュ集合に格納
    unordered_set<int> h;
    for (int i = 0; i < size2; i++){
        h.insert(arr_2[i]);
    }
    // 配列の各要素を走査し、その約数を調べる
    for (int i = 0; i < size1; i++){
        for (int j = 1; j * j <= arr_1[i]; j++){
            if (arr_1[i] % j == 0){
                // ハッシュ集合 h を使って、その約数が
                // 第2配列に存在するかどうかを確認する
                if ((h.find(j) != h.end()) || (h.find(arr_1[i] / j) != h.end())){
                    result++;
                    break;
                }
            }
        }
    }
    return result;
}
// メイン関数
int main(){
    int arr_1[] = { 1, 2, 3, 4, 5 };
    int arr_2[] = { 2, 6, 12, 15 };
    int size1 = sizeof(arr_1) / sizeof(arr_1[0]);
    int size2 = sizeof(arr_2) / sizeof(arr_2[0]);
    cout << "count is " << totalelements(arr_1, size1, arr_2, size2);
    return 0;
}

出力

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

count is 2

このアルゴリズムでは、各要素の約数を √n まで試し割りすることで計算量を抑えつつ、unordered_set による O(1) の平均検索時間を活用して、約数が第2配列に存在するかどうかを効率的に判定しています。