C++で連結リスト内の最小値・最大値の素数を求める方法

問題文

n個の正の整数からなる連結リストが与えられます。このリストの中から、値が最小の素数と最大の素数を見つける必要があります。

例えば、次のようなリストが与えられた場合 −

10 -> 4 -> 1 -> 12 -> 13 -> 7 -> 6 -> 2 -> 27 -> 33
この場合、最小の素数は 2、最大の素数は 13 となります

アルゴリズム

1. 与えられた数の中から最大値を求める（これを maxNumber と呼ぶ）
2. 1 から maxNumber までの素数を生成し、動的配列に格納する
3. 連結リストを走査し、動的配列を参照して最小値・最大値の素数を特定する

実装のポイント

このアルゴリズムでは、指定された範囲までの素数をまとめて求められる「エラトステネスの篩（ふるい）」を活用しています。まずリスト内の最大値を基準に素数テーブルを一度だけ作成すれば、あとはリストを1回走査するだけで最小・最大の素数を効率的に判定できます。素数判定を要素ごとに行う方法と比べ、計算量を大幅に抑えられるのが大きなメリットです。

コード例

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <list>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
void printMinAndMaxPrimes(list<int> intList){
   int maxNumber = *max_element(intList.begin(),
   intList.end());
   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 (auto it = intList.begin(); it != intList.end(); ++it) {
      if (primes[*it]) {
         minPrime = min(minPrime, *it);
         maxPrime = max(maxPrime, *it);
      }
   }
   cout << "Prime number of min value = " << minPrime << "\n";
   cout << "Prime number of max value = " << maxPrime << "\n";
}
int main(){
   int arr [] = {10, 4, 1, 12, 13, 7, 6, 2, 27, 33};
   list<int> intList(arr, arr + SIZE(arr));
   printMinAndMaxPrimes(intList);
   return 0;
}

コードの解説

まず max_element 関数でリスト内の最大値を取得し、その値を上限として vector<bool> 型の素数テーブルを作成します。0 と 1 は素数ではないため false に設定し、2 から順に合成数をふるい落としていきます。その後、リストを先頭から走査し、素数テーブルで true となっている要素だけを対象に、最小値（minPrime）と最大値（maxPrime）を更新していきます。

出力結果

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

Prime number of min value = 2
Prime number of max value = 13