C++에서 주어진 범위의 소수 간의 최대 차이에 대한 쿼리

이 문제에서는 두 개의 값 L과 R로 구성된 Q 쿼리가 제공됩니다. 우리의 임무는 C++에서 주어진 범위의 소수 간의 최대 차이에 대한 쿼리를 푸는 프로그램을 만드는 것입니다.

문제 설명:여기에서 각 쿼리에서 두 개의 값 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