C++の特定の範囲の素数間の最大差のクエリ

この問題では、2つの値LとRで構成されるQクエリが与えられます。私たちのタスクは、C++の特定の範囲の素数間の最大差についてクエリを解決するプログラムを作成することです。

問題の説明：ここでは、各クエリで、2つの値LとRが与えられています。最大の差、つまり、指定された範囲内の最大の素数と最小の素数の差を見つける必要があります。

問題を理解するために例を見てみましょう

入力

Q = 2
2 45
14 16
41 0

出力

説明

クエリ1の場合、指定された範囲内の最小の素数は2で、最大の素数は43です。差43-2=41。

クエリ2の場合、指定された範囲内に素数がないため、出力は0です。

ソリューションアプローチ

To solve the problem, we will create an array of prime numbers till 100005
which is the given range. Then, we will find the first prime number which is
greater than L and the first prime number which is smaller than R . and find
their difference.

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;

bool primeNumber[100005] ;

void findPrimes(){
   memset(primeNumber, true, sizeof(primeNumber));
   for (int i = 2; i * i < 100005; i++) {
      if (primeNumber[i]) {
         for (int j = i + i; j < 100005; j += i)
         primeNumber[j] = false;
      }
   }
}

int findPrimeInRange(int L, int R) {

   int LPrime = 0;
   int RPrime = 0;
   for(int i = L; i <= R; i++){
      if(primeNumber[i] == true){
         LPrime = i;
         break;
      }
   }
   for(int j = R; j >= L; j--){
      if(primeNumber[j] == true){
         RPrime = j;
         break;
      }
   }
   return (RPrime - LPrime);
}

int main() {
   int Q = 3;
   int query[Q][2] = {{4, 15}, {32, 37}, {54, 1100}};
   findPrimes();
   for (int i = 0; i < Q; i++)
   cout<<"For query "<<(i+1)<<": The maximum difference between primes numbers is "<<findPrimeInRange(query[i][0], query[i][1])<<"\n";
   return 0;
}

出力

For query 1: The maximum difference between primes numbers is 8
For query 2: The maximum difference between primes numbers is 0
For query 3: The maximum difference between primes numbers is 1038