Truy vấn cho sự khác biệt lớn nhất giữa các số nguyên tố trong các phạm vi nhất định trong C ++

Trong bài toán này, chúng tôi đưa ra các truy vấn Q bao gồm hai giá trị L và R. Nhiệm vụ của chúng tôi là tạo một chương trình để giải các Truy vấn cho sự khác biệt lớn nhất giữa các số nguyên tố trong các phạm vi đã cho trong C ++.

Mô tả vấn đề:Ở đây, trong mỗi quả mọng, chúng ta được cung cấp hai giá trị L vàR. Chúng ta phải tìm hiệu số lớn nhất, tức là hiệu số giữa số nguyên tố lớn nhất và số nguyên tố nhỏ nhất trong phạm vi đã cho.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

Q = 2
2 45
14 16
41 0

Đầu ra

Giải thích

Đối với truy vấn 1, số nguyên tố nhỏ nhất trong phạm vi đã cho là 2 và số lớn nhất là 43. Hiệu số 43 - 2 =41.

Đối với truy vấn 2, không có số nguyên tố nào trong phạm vi đã cho, do đó thông lượng theo đầu ra là 0.

Cách tiếp cận giải pháp,

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.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

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