数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在给定 C++ 范围中的质数之间最大差值的查询
在本问题中，我们给出了 Q 个查询，其中包含两个值 L 和 R。我们的任务是创建一个程序来解决 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
更新时间： 2020 年 9 月 9 日
354 次浏览
广告