दो संख्याओं के जोड़े जिनका योग अभाज्य संख्या है और n से कम है, उनकी गणना करने का C++ प्रोग्राम

समस्या विवरण

हमें एक धनात्मक संख्या n दी गई है। लक्ष्य उन जोड़ों (i, j) की गणना करना है जहाँ:

• i + j अभाज्य संख्या है
• i + j < n
• i != j और i, j ≥ 1

उदाहरण

इनपुट: n = 7

आउटपुट: 3

व्याख्या: जोड़े: (1,2), (1,4), (2,3)। योग: 3, 5, 5 — सभी अभाज्य और 7 से कम।

इनपुट: n = 10

आउटपुट: 6

व्याख्या: जोड़े: (1,2), (1,4), (2,3), (1,6), (2,5), (3,4)। योग: 3, 5, 5, 7, 7, 7।

दृष्टिकोण

हम n से कम सभी अभाज्य संख्याएँ खोजने के लिए सुंदरम की छलनी (Sieve of Sundaram) का उपयोग करते हैं। प्रत्येक विषम संख्या temp के लिए, जिन जोड़ों का योग temp होता है, उनकी संख्या temp/2 होती है। 2 को छोड़कर सभी अभाज्य संख्याएँ विषम होती हैं, इसलिए प्रत्येक अभाज्य संख्या temp < n के लिए हम temp/2 को गणना में जोड़ते हैं।

एल्गोरिदम

1. चर n लें
2. फंक्शन prime_pair(int n) जोड़ों की संख्या लौटाता है
3. प्रारंभिक गणना = 0
4. सुंदरम की छलनी 2*n+2 से कम अभाज्य संख्याएँ उत्पन्न करती है, इसलिए n को आधा करके temp_2 में स्टोर करें
5. बूलियन ऐरे check[] बनाएँ और false से आरंभ करें
6. फंक्शन check_prime() से i+j+2*i*j रूप की संख्याओं को true चिह्नित करें
7. check[] को पार करें: प्रत्येक check[i] == false के लिए, अभाज्य संख्या temp = 2*i + 1
8. count += temp/2 जोड़ें
9. गणना लौटाएँ

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

void check_prime(bool check[], int temp) {
    for (int i = 1; i <= temp; i++) {
        for (int j = i; (i + j + 2*i*j) <= temp; j++) {
            check[i + j + 2*i*j] = true;
        }
    }
}

int prime_pair(int n) {
    int count = 0;
    int temp_2 = (n - 2) / 2;
    vector<bool> check(temp_2 + 1, false);
    check_prime(check.data(), temp_2);
    
    for (int i = 1; i <= temp_2; i++) {
        if (!check[i]) {
            int temp = 2*i + 1;
            count += (temp / 2);
        }
    }
    return count;
}

int main() {
    int n = 10;
    cout << "Count: " << prime_pair(n);
    return 0;
}

आउटपुट

Count: 6