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

問題の概要

この問題では、n個の整数からなる配列 arr[] が与えられます。

私たちの課題は、配列の要素を最も多く割り切る整数を見つけることです。

問題の説明: 配列の要素を最大数だけ割り切ることができる数 p を求める必要があります。該当する数が複数存在する場合は、より小さい方の値を返します。

具体例で理解しよう

入力: arr[] = {4, 5, 6, 7, 8}

出力: 2

説明:

数値 2 は {4, 6, 8} の3つの要素を割り切ることができます。つまり、配列の中で最も多くの要素を割り切るのは 2 というわけです。

解法のアプローチ

1. 単純な全探索

最もシンプルな解決策は、配列を走査し、1からkまでの各数値について、配列内の各要素を実際に割ってみる方法です。そして、最も多くの要素を割り切れた数値を答えとして返します。ただし、この方法は二重ループが必要となるため、計算量が増えてしまうという欠点があります。

2. 素因数分解を活用した効率的な方法

もう一つのアプローチは、「配列のすべての要素は必ずその素因数で割り切れる」という性質を利用するものです。

具体的には、各素数で割り切れる要素の出現頻度を記録し、最も頻度の高い素因数を答えとして返します。素数とその出現頻度はハッシュマップに格納して管理します。

さらに、エラトステネスのふるいを用いて各数値の最小の素因数を事前に計算しておくことで、素因数分解を高速に行うことができます。

解法を実装したプログラム

コード例

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

#define MAXN 100001
int primes[MAXN];

void findPrimeSieve()
{
    primes[1] = 1;
    for (int i = 2; i < MAXN; i++)
        primes[i] = i;
    for (int i = 4; i < MAXN; i += 2)
        primes[i] = 2;

    for (int i = 3; i * i < MAXN; i++) {
        if (primes[i] == i) {
            for (int j = i * i; j < MAXN; j += i)
                if (primes[j] == j)
                    primes[j] = i;
        }
    }
}

vector<int> findFactors(int num)
{
    vector<int> factors;
    while (num != 1) {
        int temp = primes[num];
        factors.push_back(temp);
        while (num % temp == 0)
            num = num / temp;
    }
    return factors;
}

int findmaxDivElement(int arr[], int n) {

    findPrimeSieve();
    map<int, int> factorFreq;
    for (int i = 0; i < n; ++i) {

        vector<int> p = findFactors(arr[i]);
        for (int i = 0; i < p.size(); i++)
            factorFreq[p[i]]++;
    }

    int cnt = 0, ans = 1e+7;
    for (auto itr : factorFreq) {
        if (itr.second >= cnt) {
            cnt = itr.second;
            ans > itr.first ? ans = itr.first : ans = ans;
        }
    }

    return ans;
}

int main() {

    int arr[] = { 4, 5, 6, 7, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The number that divides the maximum elements of the array is "<<findmaxDivElement(arr, n);
    return 0;
}

出力結果

The number that divides the maximum elements of the array is 2

出力は「配列の要素を最も多く割り切る数は 2 である」ことを示しています。

まとめ

このように、素因数分解とエラトステネスのふるいを組み合わせることで、配列内の各要素を個別に試す全探索よりも効率的に、「最も多くの要素を割り切る整数」を求めることができます。要素数や値の範囲が大きい場合には、特に有効なアプローチといえるでしょう。