दी गई सरणी से सबसे बड़ा उपसमुच्चय ढूंढना जिसमें प्रत्येक जोड़े का योग एक अभाज्य संख्या हो। अधिकतम तत्व 100000 मानकर, उदाहरण के लिए -
इनपुट: nums[] = { 3, 2, 1, 1 } आउटपुट: आकार = 3, उपसमुच्चय = { 2, 1, 1 } व्याख्या: उपसमुच्चय बन सकते हैं: {3, 2}, {2, 1} और { 2, 1, 1}, {2, 1, 1} में जोड़ी (2,1) का योग 3 है जो अभाज्य है, और जोड़ी (1,1) का योग 2 है जो भी एक अभाज्य संख्या है। इनपुट: nums[] = {1, 4, 3, 2} आउटपुट: आकार = 2, उपसमुच्चय = {1, 4} व्याख्या: उपसमुच्चय बन सकते हैं: {1, 4}, {4, 3}, और {3, 2} सभी आकार 2 के हैं इसलिए हम कोई भी उपसमुच्चय ले सकते हैं जैसे 1 + 4 = 5 जो एक अभाज्य संख्या है।समाधान खोजने का दृष्टिकोण
यह जांचने के लिए कि क्या जोड़ा अभाज्य है, पहले हमें जांचना होगा कि इसका योग विषम है या सम क्योंकि सम संख्याएं 2 को छोड़कर अभाज्य नहीं होती हैं। और दो संख्याओं का योग सम हो सकता है यदि दोनों संख्याएं या तो विषम हैं या सम।
इस समस्या में, हम तीन संख्याएं लेंगे, x, y, और z, जहां किन्हीं दो संख्याओं को या तो सम या विषम होना चाहिए। फिर हम इस उपसमुच्चय को अभाज्य योग जोड़े के लिए चेक करेंगे, और यह संभव हो सकता है यदि,
उपसमुच्चय में कुछ 1 की संख्या और कुछ अन्य संख्याएं हैं जिनमें NUM + 1 अभाज्य होना चाहिए।
या यदि उपसमुच्चय में केवल दो संख्याएं हैं जिनका योग अभाज्य है।
उदाहरण
#include <bits/stdc++.h> using namespace std; #define M 100001 bool check_prime[M] = { 0 }; int sieve_of_eratosthenes(){ for (int p = 2; p * p < M; p++){ // यदि चिह्नित नहीं है तो चिह्नित करें if (check_prime[p] == 0){ // p के सभी गुणकों को अपडेट करें for (int i = p * 2; i < M; i += p) check_prime[i] = 1; } } return 0; } int main(){ sieve_of_eratosthenes(); int nums[] = { 3, 2, 1, 1}; int n = sizeof(nums) / sizeof(nums[0]); int ones = 0; for (int i = 0; i < n; i++) if (nums[i] == 1) ones++; // यदि 1 मौजूद हैं और // 0 से बड़े तत्व भी मौजूद हैं if (ones > 0){ for (int i = 0; i < n; i++){ //जांचना कि num + 1 अभाज्य है या नहीं if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){ cout << ones + 1 << endl; // nums[i] के साथ मौजूद सभी 1 प्रिंट करना for (int j = 0; j < ones; j++) cout << 1 << " "; cout << nums[i] << endl; return 0; } } } // यदि उपसमुच्चय में केवल 1 हैं if (ones >= 2){ cout << ones << endl; for (int i = 0; i < ones; i++) cout << 1 << " "; cout << endl; return 0; } // यदि कोई 1 मौजूद नहीं है। for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j++){ // अभाज्य योग वाले पूर्णांक जोड़े की खोज। if (check_prime[nums[i] + nums[j]] == 0){ cout << 2 << endl; cout << nums[i] << " " << nums[j] << endl; return 0; } } } // यदि सरणी में केवल एक तत्व मौजूद है। cout << -1 << endl; return 0; }आउटपुट
3 1 1 2
उपरोक्त कोड की व्याख्या
सबसे पहले हम सरणी में 1 की संख्या चेक कर रहे हैं।
यदि यह 0 से अधिक है, तो सरणी को पार करें और 1 के अलावा प्रत्येक तत्व की जांच करें कि क्या nums[i] + 1 अभाज्य है; यदि हां, तो उपसमुच्चय के आकार के रूप में (ones + 1) की कुल संख्या प्रिंट करें और संख्या के साथ सभी 1।
यदि दी गई सरणी में केवल 1 हैं, तो सभी 1 प्रिंट करें क्योंकि सभी जोड़ों का योग 2 (अभाज्य) होगा।
यदि कोई 1 मौजूद नहीं है, तो सरणी में प्रत्येक जोड़े की जांच करें जिसका योग अभाज्य हो।
अन्यथा -1 प्रिंट करें।
निष्कर्ष
इस ट्यूटोरियल में, हमने एक समस्या पर चर्चा की जहां हमें दी गई सरणी से सबसे बड़ा उपसमुच्चय ढूंढना है जिसमें प्रत्येक जोड़े का योग अभाज्य हो। हमने इस समस्या को हल करने के लिए एराटोस्थनीज की छलनी की मदद से और सरणी में 1 की संख्या चेक करके दृष्टिकोण पर चर्चा की। हमने इस समस्या के लिए C++ प्रोग्राम भी चर्चा की जिसे हम C, Java, Python आदि प्रोग्रामिंग भाषाओं में कर सकते हैं। आशा है आपको यह ट्यूटोरियल उपयोगी लगा होगा।
