C++で別の配列のどの要素でも割り切れない配列の要素を見つける方法

この問題では、2つの整数型配列 arr1[] と arr2[] が与えられます。私たちのタスクは、「arr2 のどの要素によっても割り切れない arr1 の要素」をすべて見つけるプログラムを作成することです。

問題の説明

arr1 に含まれる各要素について、arr2 のいずれかの要素で割り切れるかどうかを判定し、割り切れない要素だけを出力します。

入出力例で理解しよう

入力: arr1[] = {17, 15, 5, 12, 8} ／ arr2[] = {5, 4}

出力: 17

解説:

• 17 → arr2 のどの要素でも割り切れない(条件を満たす)
• 15 → 5 で割り切れる
• 5 → 5 で割り切れる
• 12 → 4 で割り切れる
• 8 → 4 で割り切れる

解法1:単純な全探索(ナイーブなアプローチ)

最も分かりやすいのは、配列を直接比較していく方法です。arr1 を順に走査し、各要素について arr2 のすべての要素で割った余りを調べます。1つでも割り切れる要素があればその要素は除外し、どこでも割り切れなければ出力します。ただし二重ループになるため計算量は O(n × m) となり、配列が大きくなると非効率です。

アルゴリズム

1. ステップ1: i を 0 から n-1 まで動かしながら arr1 をループする。
2. ステップ2: 各 arr1[i] について、j を 0 から m-1 まで動かしながら arr2 をループする。
3. ステップ3: arr1[i] % arr2[j] == 0 になったら、フラグを -1 にして内側のループを抜ける。
4. ステップ4: フラグが -1 でなければ、arr1[i] を出力する。

実装例

#include<iostream>
using namespace std;

void findEleNotDivisbleByArray(int arr1[], int arr2[], int arr1Size, int arr2Size) {

    int flag = 0;
    for (int i = 0; i < arr1Size; i++) {
        flag = 0;
        for (int j = 0; j < arr2Size; j++) {

            if (arr1[i] % arr2[j] == 0) {
                flag = -1;
                break;
            }
        }
        if (flag == 0)
            cout << arr1[i] << "\t";
    }
}

int main()
{
    int arr1[] = {17, 15, 5, 12, 23, 8};
    int arr2[] = {5, 4};
    int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
    int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
    cout << "Elements of an array that are not divisible by any element of another array are ";
    findEleNotDivisbleByArray(arr1, arr2, arr1Size, arr2Size);
    return 0;
}

実行結果

Elements of an array that are not divisible by any element of another array are 17 23

この解法は正しい結果を返しますが、効率の面では改善の余地があります。次に、より効率的な解法を見ていきましょう。

解法2:倍数へのマーキングによる効率的なアプローチ

こちらの方法では、エラトステネスの篩に似た発想を利用します。まず arr1 の最大値を求め、その値までのインデックスを持つブール型配列 mark[] を用意します。続いて、arr2 の各要素について、その倍数(最大値以下のもの)すべてに「割り切れる」印をつけていきます。最後に、印がついていない arr1 の要素だけを出力すれば完成です。

この方法なら、各 arr2 の要素ごとに倍数を一括で処理できるため、要素同士を総当たりで比較する必要がなく、全体の計算量を大幅に削減できます。

実装例

#include<iostream>
#include<vector>
using namespace std;

void findEleNotDivisibleByArray(int arr1[], int arr2[], int arr1Size, int arr2Size) {

    int maxEle = 0;
    for (int i = 0; i < arr1Size; i++)
        if (arr1[i] > maxEle)
            maxEle = arr1[i];

    // 割り切れた要素に印をつけるための配列
    vector<bool> mark(maxEle + 1, false);

    for (int i = 0; i < arr2Size; i++)
        for (int j = arr2[i]; j <= maxEle; j += arr2[i])
            mark[j] = true;

    for (int i = 0; i < arr1Size; i++)
        if (!mark[arr1[i]])
            cout << arr1[i] << endl;
}

int main()
{
    int arr1[] = {17, 15, 5, 12, 8};
    int arr2[] = {5, 4};
    int arr1Size = sizeof(arr1)/sizeof(arr1[0]);
    int arr2Size = sizeof(arr2)/sizeof(arr2[0]);
    cout << "Elements of an array that are not divisible by any element of another array are ";
    findEleNotDivisibleByArray(arr1, arr2, arr1Size, arr2Size);
    return 0;
}

実行結果

Elements of an array that are not divisible by any element of another array are 17

まとめ

「ある配列の要素が、別の配列のどの要素でも割り切れないか」を判定する問題は、二重ループによる全探索(O(n × m))でも解けますが、arr1 の最大値までの倍数をあらかじめマークしておく方法を使えば、より効率的に答えを求められます。データ量が多い場合や同じ判定を繰り返し行う場合には、後者のアプローチが特に有効です。