C++ में दी गई रेंज में अभाज्य संख्याओं के बीच अधिकतम अंतर के लिए क्वेरीज़

समस्या विवरण

इस समस्या में, हमें Q क्वेरीज़ दी गई हैं जिनमें दो मान L और R होते हैं। हमारा कार्य C++ में दी गई रेंज में अभाज्य संख्याओं के बीच अधिकतम अंतर के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है।

समस्या विवरण: यहां, प्रत्येक क्वेरी में, हमें दो मान L और R दिए गए हैं। हमें दी गई रेंज के भीतर सबसे बड़ी और सबसे छोटी अभाज्य संख्याओं के बीच का अंतर यानी अधिकतम अंतर ढूंढना है।

उदाहरण

इनपुट

आउटपुट

व्याख्या

क्वेरी 1 के लिए, दी गई रेंज के भीतर सबसे छोटी अभाज्य संख्या 2 है और सबसे बड़ी 43 है। अंतर 43 - 2 = 41।

क्वेरी 2 के लिए, दी गई रेंज के भीतर कोई अभाज्य संख्या नहीं है, इसलिए आउटपुट 0 है।

समाधान दृष्टिकोण

समस्या को हल करने के लिए, हम दी गई रेंज तक 100005 तक अभाज्य संख्याओं की एक सरणी बनाएंगे। फिर, हम पहली अभाज्य संख्या ढूंढेंगे जो 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 << "क्वेरी " << (i+1) << ": अभाज्य संख्याओं के बीच अधिकतम अंतर " << findPrimeInRange(query[i][0], query[i][1]) << "\n";
    return 0;
}

आउटपुट

क्वेरी 1: अभाज्य संख्याओं के बीच अधिकतम अंतर 8
क्वेरी 2: अभाज्य संख्याओं के बीच अधिकतम अंतर 0
क्वेरी 3: अभाज्य संख्याओं के बीच अधिकतम अंतर 1038