এই সমস্যাতে, আমাদের Q সংখ্যক কোয়েরি দেওয়া আছে যাতে দুটি মান L এবং R থাকে। আমাদের কাজ হলো C++-এ দেয়া রেঞ্জে প্রাইম নম্বরের ম্যাক্সিমাম পার্থক্য বের করার প্রোগ্রাম লিখা।
সমস্যা বর্ণনা: এখানে প্রতিটি কোয়েরিতে দুটি মান L এবং R দেওয়া থাকে। আমাদেরকে দেওয়া রেঞ্জের মধ্যে সবচেয়ে ছোট এবং সবচেয়ে বড় প্রাইম নম্বরের পার্থক্য বের করতে হবে।
উদাহরণ দিয়ে বুঝি,
ইনপুট
Q = 2 2 45 14 16 41 0
আউটপুট
ব্যাখ্যা
কোয়েরি ১-এ, দেওয়া রেঞ্জের মধ্যে সবচেয়ে ছোট প্রাইম নম্বর ২ এবং সবচেয়ে বড় ৪৩। পার্থক্য ৪৩ - ২ = ৪১।
কোয়েরি ২-এ, দেওয়া রেঞ্জে কোনো প্রাইম নম্বর নেই, তাই আউটপুট ০।
সমাধান পদ্ধতি,
সমস্যা সমাধানের জন্য, আমরা ১০০০০৫ পর্যন্ত প্রাইম নম্বর들의 একটি অ্যারে তৈরি করব। তারপর L-র চেয়ে বড় প্রথম প্রাইম এবং R-এর চেয়ে ছোট প্রথম প্রাইম বের করে তাদের পার্থক্য বের করব।
সমাধানের কোড উদাহরণ,
উদাহরণ
#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
