दिए गए सरणी से सबसे बड़ा उपसमुच्चय ज्ञात करना जिसमें प्रत्येक जोड़ी का योग एक अभाज्य संख्या है। मान लें कि अधिकतम तत्व 100000 है, उदाहरण के लिए -
Input: nums[ ] = { 3, 2, 1,1 }
Output: size = 3, subset = { 2, 1, 1 }
Explanation:
Subsets can be formed: {3, 2}, {2, 1} and { 2, 1, 1},
In {2, 1, 1} sum of pair (2,1) is 3 which is prime,
and the sum of pairs (1,1) is 2 which is also a prime number.
Input: nums[ ] = {1, 4, 3, 2}
Output: size = 2, subset = {1, 4}
Explanation:
subset can be formed: {1, 4}, {4, 3}, and {3, 2}
All are of size 2 so we can take any subset like 1 + 4 =5 which is a prime number. समाधान खोजने के लिए दृष्टिकोण
यह पता लगाने के लिए कि क्या युग्म पहले अभाज्य है, हमें यह जाँचने की आवश्यकता है कि क्या इसका योग विषम है या सम संख्याएँ अभाज्य नहीं हैं, 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 it is not marked then mark
if (check_prime[p] == 0){
// Update all multiples of 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++;
// If ones are present and
// elements greater than 0 are also present
if (ones > 0){
for (int i = 0; i < n; i++){
//checking whether num + 1 is prime or not
if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){
cout << ones + 1 << endl;
// printing all the ones present with nums[i]
for (int j = 0; j < ones; j++)
cout << 1 << " ";
cout << nums[i] << endl;
return 0;
}
}
}
// If subsets contains only 1's
if (ones >= 2){
cout << ones << endl;
for (int i = 0; i < ones; i++)
cout << 1 << " ";
cout << endl;
return 0;
}
// If no ones are present.
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
// searching for pair of integer having sum prime.
if (check_prime[nums[i] + nums[j]] == 0){
cout << 2 << endl;
cout << nums[i] << " " << nums[j] << endl;
return 0;
}
}
}
// If only one element is present in the array.
cout << -1 << endl;
return 0;
} आउटपुट
3 1 1 2
उपरोक्त कोड की व्याख्या
-
सबसे पहले हम सरणी में संख्या की जाँच कर रहे हैं।
-
यदि यह 0 से अधिक है, तो सरणी के माध्यम से पार करें और एक के अलावा प्रत्येक तत्व की जांच करें कि क्या nums[i] + 1 अभाज्य है; यदि हां, तो (एक + 1) की कुल संख्या को सबसेट के आकार के रूप में प्रिंट करें और सभी संख्या के साथ।
-
यदि दिए गए सरणी में केवल एक है, तो सभी को प्रिंट करें क्योंकि सभी जोड़ियों का योग 2(अभाज्य) होगा।
-
यदि कोई मौजूद नहीं है, तो सरणी में प्रत्येक जोड़ी को सम अभाज्य के साथ जांचें।
-
अन्य प्रिंट -1.
निष्कर्ष
इस ट्यूटोरियल में, हमने एक समस्या पर चर्चा की जहां हमें दिए गए सरणी से सबसे बड़ा सबसेट खोजने की आवश्यकता है जिसमें प्रत्येक जोड़ी का योग प्रमुख है। हमने एराटोस्थनीज की छलनी की मदद से इस समस्या को हल करने के लिए और सरणी में लोगों की संख्या की जांच करने के लिए एक दृष्टिकोण पर चर्चा की। हमने इस समस्या के लिए C++ प्रोग्राम पर भी चर्चा की जिसे हम प्रोग्रामिंग भाषाओं जैसे C, Java, Python, आदि के साथ कर सकते हैं। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगेगा।