हमें इनपुट के रूप में एक सकारात्मक संख्या n दी गई है। लक्ष्य संभावित जोड़े (i,j) की संख्या ज्ञात करना है जैसे कि प्रत्येक जोड़ी में योग (i+j) होता है जो कि अभाज्य है और n से कम है। साथ ही i !=j और i,j>=1 यदि n 4 है तो केवल 1 युग्म संभव है जो (1,2) है। यहां 1+2 =3 अभाज्य है और 4 से कम है। साथ ही 1,2>=1.
आइए उदाहरणों से समझते हैं।
इनपुट - n=7
आउटपुट − एक अभाज्य संख्या और n से कम योग वाले युग्मों की संख्या − 3
. हैस्पष्टीकरण - जोड़े होंगे (1,2), (1,4), (2,3)। योग 3, 5, 5 अभाज्य हैं और 7 से कम हैं।
इनपुट - n=10
आउटपुट − एक अभाज्य संख्या और n से कम योग वाले युग्मों की संख्या − 6
. हैस्पष्टीकरण -
जोड़े होंगे (1,2), (1,4), (2,3), (1,6), (2,5), (3,4)।
योग 3, 5, 5, 7, 7, 7 अभाज्य हैं और 10 से कम हैं।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम सबसे पहले सुंदरम की छलनी का उपयोग करके n से कम सभी अभाज्य संख्याओं को फ़ंक्शन check_prime(bool check[], int temp) में पाएंगे।
साथ ही प्रत्येक विषम संख्या अस्थायी के लिए, अलग-अलग युग्मों की संख्या जिनका योग अस्थायी है, अस्थायी/2 होगा।
2 को छोड़कर सभी अभाज्य संख्याएँ विषम हैं इसलिए यदि हमें n से कम कोई अभाज्य संख्या मिलती है तो हम जोड़े की संख्या में अस्थायी/2 जोड़ देंगे।
-
वेरिएबल n को इनपुट के रूप में लें।
-
फ़ंक्शन prime_pair(int n) n लेता है और योग के साथ जोड़े की संख्या को एक प्रमुख संख्या और n से कम के रूप में देता है।
-
प्रारंभिक गणना 0 के रूप में लें।
-
चूंकि सुंदरम की चलनी इनपुट n के लिए 2*n+2 से कम अभाज्य संख्याएँ उत्पन्न करती है। हम n को घटाकर उसका आधा कर देते हैं और temp_2 में स्टोर कर लेते हैं।
-
प्रपत्र के सभी नंबरों (i+j+2*i*j ) को सही के रूप में चिह्नित करने के लिए लंबाई temp_2 की एक सरणी जांचें [] बनाएं। इसे सभी तत्वों के साथ असत्य के रूप में प्रारंभ करें।
-
फ़ंक्शन check_prime (बूल चेक [], int अस्थायी) का उपयोग करके, फ़ॉर्म की संख्याओं के लिए सत्य के साथ चेक [] प्रारंभ करें (i + j + 2 * i * j)। और यह योग <अस्थायी।
-
अब इंडेक्स i=0 से i
-
प्रत्येक चेक के लिए [i] असत्य के रूप में, अभाज्य संख्या होगी temp=2*i+1.
-
जो जोड़े अस्थायी रूप से जुड़ते हैं वे अस्थायी/2 होंगे।
-
गिनने के लिए अस्थायी/2 जोड़ें।
-
लूप के अंत में हमारे पास कुल जोड़ियां होंगी जिनका योग अभाज्य होगा और n से कम होगा।
-
परिणाम के रूप में वापसी की गिनती।
उदाहरण
#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;
int temp_2 = (n-2)/2;
bool check[temp_2 + 1];
memset(check, false, sizeof(check));
check_prime(check, temp_2);
for (int i=1; i <= temp_2; i++){
if (check[i] == false){
temp = 2*i + 1;
count += (temp / 2);
}
}
return count;
}
int main(){
int n = 10;
cout<<"Count of pairs with sum as a prime number and less than n are: " <<prime_pair(n);
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Count of pairs with sum as a prime number and less than n are: 6