इस लेख में, हम C++ का उपयोग करके किसी सरणी में अभाज्य युग्मों की संख्या ज्ञात करने के बारे में सब कुछ समझाएंगे। हमारे पास पूर्णांकों की एक सरणी गिरफ्तारी [] है, और हमें इसमें मौजूद सभी संभावित अभाज्य युग्मों को खोजने की आवश्यकता है। तो यहाँ समस्या का उदाहरण है -
Input : arr[ ] = { 1, 2, 3, 5, 7, 9 }
Output : 6
From the given array, prime pairs are
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)
Input : arr[] = {1, 4, 5, 9, 11}
Output : 1 समाधान खोजने के लिए दृष्टिकोण
ब्रूट फ़ोर्स अप्रोच
अब हम सभी के सबसे बुनियादी दृष्टिकोण पर चर्चा करेंगे, अर्थात, जानवर बल दृष्टिकोण, और दूसरा दृष्टिकोण खोजने का प्रयास करें क्योंकि यह दृष्टिकोण बहुत कुशल नहीं है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
bool p[MAX+1];
memset(p, true, sizeof(p));
p[1] = false;
p[0] = false;
for(int i = 2; i * i <= MAX; i++){
if(p[i] == true){
for(int j = i*2; j <= MAX; j += i){
p[j] = false;
}
}
}
for(int i = 0; i < n; i++){
if(p[arr[i]] == true)
prime[i] = true;
}
}
int main(){
int arr[] = {1, 2, 3, 5, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
int answer = 0; // counter variable to count the number of prime pairs.
int MAX = INT_MIN; // Max element
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
bool prime[n]; // boolean array that tells if the element is prime or not.
memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
seiveOfEratosthenes(arr, prime, n, MAX);
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(prime[i] == true && prime[j] == true)
answer++;
}
}
cout << answer << "\n";
return 0;
} आउटपुट
6
इस दृष्टिकोण में, हम एक बूल सरणी बना रहे हैं जो हमें बताएगी कि कोई तत्व अभाज्य है या नहीं, और फिर हम सभी संभावित युग्मों के माध्यम से जा रहे हैं और जाँच कर रहे हैं कि जोड़ी में दोनों संख्याएँ अभाज्य हैं या नहीं। यदि प्राइम है, तो उत्तर को एक-एक करके बढ़ाएँ और आगे बढ़ें।
लेकिन यह दृष्टिकोण बहुत कुशल नहीं है क्योंकि इसकी समय जटिलता O(N*N) . है , जहां N हमारे सरणी का आकार है, इसलिए अब हम इस दृष्टिकोण को और तेज़ करने जा रहे हैं।
कुशल दृष्टिकोण
इस दृष्टिकोण में, अधिकांश कोड समान होंगे, लेकिन महत्वपूर्ण परिवर्तन यह है कि सभी संभावित जोड़ियों के माध्यम से जाने के बजाय, हम केवल एक सूत्र का उपयोग करके उनकी गणना करने जा रहे हैं।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
bool p[MAX+1];
memset(p, true, sizeof(p));
p[1] = false;
p[0] = false;
for(int i = 2; i * i <= MAX; i++){
if(p[i] == true){
for(int j = i*2; j <= MAX; j += i){
p[j] = false;
}
}
}
for(int i = 0; i < n; i++){
if(p[arr[i]] == true)
prime[i] = true;
}
}
int main(){
int arr[] = {1, 2, 3, 5, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
int answer = 0; // counter variable to count the number of prime pairs.
int MAX = INT_MIN; // Max element
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
bool prime[n]; // boolean array that tells if the element is prime or not.
memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
seiveOfEratosthenes(arr, prime, n, MAX);
for(int i = 0; i < n; i++){
if(prime[i] == true)
answer++;
}
answer = (answer * (answer - 1)) / 2;
cout << answer << "\n";
return 0;
} आउटपुट
6
जैसा कि आप देख सकते हैं, अधिकांश कोड पिछले दृष्टिकोण के समान है, लेकिन महत्वपूर्ण परिवर्तन जिसने हमारी जटिलता को काफी कम कर दिया है, वह सूत्र है जिसका हमने उपयोग किया है, अर्थात, n(n-1)/2, जो हमारी संख्या की गणना करेगा प्रमुख जोड़े।
उपरोक्त कोड की व्याख्या
इस कोड में, हम एरेटोस्थनीज की छलनी का उपयोग सभी अभाज्य संख्याओं को चिह्नित करने के लिए कर रहे हैं जब तक कि हमारे पास सरणी में अधिकतम तत्व न हो। एक अन्य बूल सरणी में, हम इंडेक्स-वार तत्वों को चिह्नित कर रहे हैं कि वे अभाज्य हैं या नहीं।
अंत में, हम पूरे सरणी के माध्यम से यात्रा कर रहे हैं, मौजूद अभाज्य संख्याओं की कुल संख्या का पता लगा रहे हैं, और सूत्र n*(n-1)/2 का उपयोग करके सभी संभावित जोड़े ढूंढ रहे हैं। इस फ़ॉर्मूले के साथ, हमारी जटिलता O(N) . तक कम हो जाती है , जहां N हमारे सरणी का आकार है।
निष्कर्ष
इस लेख में, हम ओ (एन) समय जटिलता में एक सरणी में मौजूद प्रमुख जोड़े की संख्या को खोजने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (सामान्य और कुशल) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे C, java, python, और अन्य भाषाओं में लिख सकते हैं।