ในปัญหานี้ เราได้รับคิวรี 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
