在这个问题中,我们给了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