এই নিবন্ধে, আমরা 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 হল আমাদের অ্যারের আকার।
উপসংহার
এই নিবন্ধে, আমরা O(n) সময় জটিলতার একটি অ্যারেতে উপস্থিত মৌলিক জোড়ার সংখ্যা খুঁজে পেতে একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষায় যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি।
