查询C ++中给定范围内素数之间的最大差异

• Z时代
• 2024-01-10
• 分类：综合

在这个问题中，我们给了Q查询，它们由两个值L和R组成。我们的任务是创建一个程序来解决C ++中给定范围内素数之间最大差的查询。

问题描述：在这里，在每个Querry中，我们给定两个值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

以上是 查询C ++中给定范围内素数之间的最大差异 的全部内容， 来源链接： utcz.com/z/316458.html