C++でA[i] mod Kが最大になるような配列内の素数Kを見つける方法

問題の概要

n個の整数からなる配列Aが与えられたとします。この中から要素Kを見つけます。Kは素数であり、考えられるすべてのKの中でA[i] mod Kの値が最大になるものを選びます。条件を満たす数が見つからない場合は、-1を返します。

例えば、A = [2, 10, 15, 7, 6, 8, 13] の場合、出力は13になります。この配列には3つの素数（2、7、13）が含まれており、それぞれの剰余の最大値は以下のようになります。

• K = 2 の場合：15 mod 2 = 1
• K = 7 の場合：6 mod 7 = 6
• K = 13 の場合：10 mod 13 = 10

この中で最も大きいのは10なので、答えは13となります。

アプローチ：最大の素数を見つける

A[i] mod K の値を最大化するためには、Kは配列内の最大の素数である必要があります。また、A[i]はKより小さい配列内の最大の要素でなければなりません。したがって、この問題は「配列内の最大の素数を見つける」というシンプルな問題に帰着できます。

具体的な手順は以下の通りです。

1. 配列の最大要素を求める
2. エラトステネスの篩を使って、最大要素以下のすべての素数を列挙する
3. 配列内に実際に存在する素数の中から最大のものを出力する
4. 素数が一つも存在しない場合は -1 を返す

C++での実装例

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int getMaxPrime(int arr[], int n) {
    int max_elem = *max_element(arr, arr + n);
    vector<bool> prime_vals(max_elem + 1, true);
    prime_vals[0] = false;
    prime_vals[1] = false;
    for (int p = 2; p * p <= max_elem; p++) {
        if (prime_vals[p] == true) {
            for (int i = p * 2; i <= max_elem; i += p)
            prime_vals[i] = false;
        }
    }
    int maximum = -1;
    for (int i = 0; i < n; i++) {
        if (prime_vals[arr[i]])
        maximum = max(maximum, arr[i]);
    }
    return maximum;
}
int main() {
    int arr[] = { 2, 10, 15, 7, 6, 8, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Max prime is: " << getMaxPrime(arr, n);
}

実行結果

Max prime is: 13

コードの解説

1. エラトステネスの篩による素数判定

まず max_element 関数で配列の最大値を取得し、そのサイズ分のbool型ベクター prime_vals を作成します。初期値はすべて true（素数候補）とし、0と1は素数ではないため false に設定します。次に、2から √max_elem までの各数値 p について、p が素数であればその倍数をすべて false にマークしていきます。これにより、最大要素以下のすべての素数を効率的に判定できます。

2. 配列内の最大素数の検索

篩の処理が完了したら、配列の各要素について prime_vals を参照し、素数かどうかを確認します。素数であれば、これまでの最大値と比較して更新します。最終的に maximum 変数に格納された値が答えとなり、素数が一つも見つからなかった場合は初期値の -1 がそのまま返されます。

計算量

エラトステネスの篩の計算量は O(M log log M) です（Mは配列の最大要素）。その後の配列走査は O(n) なので、全体の時間計算量は O(M log log M + n)、空間計算量は O(M) となります。