最大数C++の配列内の連続する素数の数

素数は、1と数自体の2つの要素しかないものです。 1,2,3,5,7,11,13…。は素数ですが、4,6,8,9,10….20は素数ではありません。すべての非素数には2つ以上の要素があります。例を挙げて理解しましょう。

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

出力 − 3

説明 −上記の配列の素数は3,5,2,7,13です。隣接する番号は3、5、2、7、13です。最長のシーケンスには3つの数字があります。したがって、答えは4です。

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

出力 − 3

説明 −上記の配列の素数は5,7,17​​,31,41です。隣接する番号は5、7、17です。最長のシーケンスには3つの数字があります。したがって、答えは3です。

以下のプログラムで使用されているアプローチは次のとおりです

• 整数配列Arr[]は、素数と非素数を格納するために使用されます。

• 関数isprime（int num）は、numが素数であるかどうかをチェックするために使用されます。素数の場合は、半分に達するまで要素がないはずです。

• 素数の場合、isprime（）は1を返し、それ以外の場合は0を返します。

• 関数primeSubarray（int arr []、int n）は、2つの入力パラメーターを取ります。数値の配列自体、そのサイズ。連続する素数の最長シーケンスのサイズを返します。

• 最初からarr[]の数字をトラバースします。 arr [i]が非プライムの場合（isprime（arr [i]）==0）。次に、連続する素数の数を0に変更します。

• 素数の場合は、素数の数を増やします。 （非プライムが検出された場合は、0から再開されます）

• カウントがこれまでに最大であるかどうかを確認します。最大である場合は、その値をmaxCに保存します。

• 結果としてmaxCを返します。

例

#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; //if both failed then num is prime
}
int primeSubarray(int arr[], int n){
   int count=0;
   int maxSeq=0;
   for (int i = 0; i < n; i++) {
      // if non-prime
      if (isprime(arr[i]) == 0)
         count = 0;
         //if prime
      else {
         count++;
         //printf("\n%d",arr[i]); print prime number subsequence
         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