C++で配列内の連続する素数の最大数を求める方法

本記事では、ランダムな順序で並んだ整数の配列（サイズ N）の中から、連続して出現する素数の最長列を見つける方法を解説します。素数と非素数が混在する配列を走査し、最も長く続いた素数の個数を求めるのが目標です。

素数とは、1とその数自身という2つの約数しか持たない数のことです。1、2、3、5、7、11、13などは素数であり、一方で4、6、8、9、10などの合成数は2つより多くの約数を持ちます。それでは、具体例で確認してみましょう。

入力例と出力例

入力 − Arr[] = { 1,3,5,2,6,7,13,4,9,10 }

出力 − 3

説明 − この配列に含まれる素数は 3,5,2,7,13 です。このうち配列上で隣接しているのは「3,5,2」と「7,13」の2か所で、最も長い列は3個の素数から構成されます。したがって答えは3です。

入力 − Arr[] = { 5,7,17,27,31,21,41 }

出力 − 3

説明 − 素数は 5,7,17,31,41 ですが、配列上で隣接しているのは先頭の「5,7,17」だけです。最長の連続列は3個なので、答えは3になります。

プログラムで使用するアプローチ

• 整数配列 Arr[] に素数・非素数を格納します。
• 関数 isprime(int num) は、num が素数かどうかを判定します。2から num の半分までの間に約数がひとつも存在しなければ、その数は素数とみなせます。
• 素数であれば isprime() は 1 を返し、そうでなければ 0 を返します。
• 関数 primeSubarray(int arr[], int n) は、配列自身とそのサイズを引数に受け取り、連続する素数の最長列の長さを返します。
• 配列 arr[] を先頭から順に走査し、arr[i] が非素数なら（isprime(arr[i]) == 0）、連続カウントを 0 にリセットします。
• 素数であればカウントを 1 増やします（途中で非素数が出現すれば、再び 0 から数え直します）。
• 現在のカウントがこれまでの最大値を上回っていれば、その値を maxSeq に保存します。
• 最後に maxSeq を結果として返します。

サンプルコード

#include <iostream>
#include <stdio.h>
int isprime(int num){
    if (num <= 1)
       return 0;
    for (int i = 2; i <= num/2; i++)
       if (num % i == 0)
          return 0;
    return 1; // どちらの条件も満たさなければ num は素数
}
int primeSubarray(int arr[], int n){
    int count=0;
    int maxSeq=0;
    for (int i = 0; i < n; i++) {
       // 非素数の場合
       if (isprime(arr[i]) == 0)
          count = 0;
       // 素数の場合
       else {
          count++;
          //printf("\n%d",arr[i]); 連続する素数列の表示用
          maxSeq=count>maxSeq?count:maxSeq;
       }
    }
    return maxSeq;
}
int main(){
    int arr[] = { 8,4,2,1,3,5,7,9 };
    int n =8;
    printf("Maximum no. of contiguous Prime Numbers in an array: %d",
    primeSubarray(arr, n));
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Maximum no. of contiguous Prime Numbers in an array : 3

この例では、配列 { 8,4,2,1,3,5,7,9 } の中で素数は 2,3,5,7 であり、この4つが連続して並んでいるため、一見すると答えは4に思えます。しかし配列の先頭側にある 1 は素数ではないため、実際には「3,5,7」の3個が最長の連続列となり、結果は3が出力されます。