इस लेख में, हम C++ का उपयोग करके सरणी में अभाज्य जोड़ों की संख्या ज्ञात करने के बारे में सब कुछ समझाएंगे। हमारे पास पूर्णांकों की एक सरणी arr[] है, और हमें इसमें मौजूद सभी संभावित अभाज्य जोड़ों को ढूंढना है। तो समस्या के लिए यहाँ उदाहरण है:
Input : arr[ ] = { 1, 2, 3, 5, 7, 9 } Output : 6 दी गई सरणी से, अभाज्य जोड़े हैं (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]); // हमारी सरणी का आकार int answer = 0; // अभाज्य जोड़ों की संख्या गिनने के लिए काउंटर चर int MAX = INT_MIN; // अधिकतम तत्व for(int i = 0; i < n; i++){ MAX = max(MAX, arr[i]); } bool prime[n]; // बूलियन सरणी जो बताती है कि तत्व अभाज्य है या नहीं memset(prime, false, sizeof(prime)); // सभी तत्वों को 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 हमारी सरणी का आकार है, इसलिए अब हम इस दृष्टिकोण को तेज़ बनाएंगे।
कुशल दृष्टिकोण
इस दृष्टिकोण में, अधिकांश कोड समान होगा, लेकिन महत्वपूर्ण परिवर्तन यह है कि सभी संभावित जोड़ों के माध्यम से जाने के बजाय, हम केवल एक सूत्र का उपयोग करके उनकी गणना करेंगे।
उदाहरण
#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]); // हमारी सरणी का आकार int answer = 0; // अभाज्य जोड़ों की संख्या गिनने के लिए काउंटर चर int MAX = INT_MIN; // अधिकतम तत्व for(int i = 0; i < n; i++){ MAX = max(MAX, arr[i]); } bool prime[n]; // बूलियन सरणी जो बताती है कि तत्व अभाज्य है या नहीं memset(prime, false, sizeof(prime)); // सभी तत्वों को 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 हमारी सरणी का आकार है।
निष्कर्ष
इस लेख में, हम O(n) समय जटिलता में सरणी में मौजूद अभाज्य जोड़ों की संख्या ज्ञात करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य और कुशल) भी सीखा जिससे हमने इस समस्या को हल किया। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं।
