প্রদত্ত অ্যারে থেকে বৃহত্তম উপসেট খুঁজে বের করতে যেখানে প্রতিটি জোড়ার যোগফল একটি মৌলিক সংখ্যা। অনুমান করা হচ্ছে সর্বাধিক উপাদান 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-এর বেশি হয়, তাহলে অ্যারের মধ্য দিয়ে যান এবং একটি ব্যতীত প্রতিটি উপাদান পরীক্ষা করুন যে সংখ্যা[i] + 1 প্রাইম কিনা; যদি হ্যাঁ, তাহলে উপসেটের আকার হিসাবে মোট সংখ্যা (একটি + 1) এবং সংখ্যা সহ সমস্ত সংখ্যা প্রিন্ট করুন৷
-
যদি প্রদত্ত অ্যারেতে শুধুমাত্র একটি থাকে, তবে সমস্ত জোড়ার যোগফল 2 (প্রাইম) হিসাবে সমস্তগুলিকে প্রিন্ট করুন৷
-
যদি কেউ উপস্থিত না থাকে, তাহলে সমষ্টি প্রাইম দিয়ে অ্যারের প্রতিটি জোড়া চেক করুন।
-
অন্যথায় প্রিন্ট -1।
উপসংহার
এই টিউটোরিয়ালে, আমরা একটি সমস্যা নিয়ে আলোচনা করেছি যেখানে আমাদের প্রদত্ত অ্যারে থেকে বৃহত্তম উপসেট খুঁজে বের করতে হবে যেখানে প্রতিটি জোড়ার যোগফল প্রাইম। আমরা Eratosthenes এর চালনীর সাহায্যে এই সমস্যাটি সমাধান করার জন্য এবং অ্যারের মধ্যে সংখ্যাগুলি পরীক্ষা করার জন্য একটি পদ্ধতি নিয়ে আলোচনা করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম নিয়েও আলোচনা করেছি যা আমরা সি, জাভা, পাইথন ইত্যাদি প্রোগ্রামিং ভাষার সাথে করতে পারি। আমরা আশা করি এই টিউটোরিয়ালটি আপনার কাজে লাগবে।
