配列内の最小値・最大値の素数を求めるC++プログラム

問題文

n個の正整数からなる配列が与えられたとき、その中に含まれる素数のうち、値が最小のものと最大のものを見つけることを考えます。

例えば、次のような配列が与えられた場合を考えてみましょう。

arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33}

この場合、最小の素数は「2」、最大の素数は「13」となります。

アルゴリズム

この問題は、あらかじめ素数表を作成しておくことで効率的に解くことができます。手順は以下の通りです。

1. 入力配列の中から最大値を求めます（maxNumber と呼びます）。
2. 1 ～ maxNumber の範囲の素数を「エラトステネスの篩」で生成し、動的配列（vector）に格納します。
3. 入力配列を走査しながら素数表を参照し、最小値・最大値となる素数を求めます。

サンプルコード

以下は、上記のアルゴリズムを実装したC++プログラムです。エラトステネスの篩により素数表を構築し、配列内の最小・最大の素数を出力します。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

void printMinAndMaxPrimes(int *arr, int n) {
    // 配列内の最大値を取得
    int maxNumber = *max_element(arr, arr + n);

    // エラトステネスの篩で素数表を作成
    vector<bool> primes(maxNumber + 1, true);
    primes[0] = primes[1] = false;
    for (int p = 2; p * p <= maxNumber; ++p) {
        if (primes[p]) {
            for (int i = p * 2; i <= maxNumber; i += p) {
                primes[i] = false;
            }
        }
    }

    // 最小・最大の素数を探索
    int minPrime = INT_MAX;
    int maxPrime = INT_MIN;
    for (int i = 0; i < n; ++i) {
        if (primes[arr[i]]) {
            minPrime = min(minPrime, arr[i]);
            maxPrime = max(maxPrime, arr[i]);
        }
    }

    cout << "最小値の素数 = " << minPrime << "\n";
    cout << "最大値の素数 = " << maxPrime << "\n";
}

int main() {
    int arr[] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33};
    printMinAndMaxPrimes(arr, SIZE(arr));
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

最小値の素数 = 2
最大値の素数 = 13

プログラムのポイント

• max_element() を使うことで、配列内の最大値を一行で取得できます。
• vector<bool> を使った素数表により、各要素が素数かどうかを O(1) で判定できます。
• エラトステネスの篩の計算量は O(N log log N) であり、要素ごとに素数判定を繰り返す方法よりも高速です。