এই আর্টিকেলে আমরা C++ ব্যবহার করে একটি অ্যারে-এ প্রাইম পেয়ার সংখ্যা বের করার সবকিছু ব্যাখ্যা করব। আমাদের কাছে একটি পূর্ণসংখ্যার অ্যারে arr[] আছে, এবং আমাদের কাজ হল সেটি থেকে সকল সম্ভাব্য প্রাইম পেয়ার বের করা। উদাহরণ:
ইনপুট : arr[ ] = { 1, 2, 3, 5, 7, 9 }
আউটপুট : 6
দেওয়া অ্যারেতে প্রাইম পেয়ারগুলো হল (2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)
ইনপুট : arr[] = {1, 4, 5, 9, 11}
আউটপুট : 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
এই পদ্ধতিতে আমরা একটি বুল অ্যারে বানাই যা বলে কোনো এলিমেন্ট প্রাইম কিনা, এবং তারপর সকল সম্ভাব্য পেয়ার traverser করি এবং চেক করি পেয়ারের দুটি সংখ্যাও প্রাইম কিনা। যদি প্রাইম হয় তবে আউটপুট এক বাড়িয়ে চলি।
কিন্তু এই পদ্ধতি খুব দক্ষ নয় কারণ এর সময় জটিলতা O(N²), যেখানে N হল আমাদের অ্যারের আকার। তাই আমরা এই পদ্ধতিকে দ্রুত করব।
দক্ষ পদ্ধতি (Efficient Approach)
এই পদ্ধতিতে কোডের অধিকাংশ একই থাকবে, কিন্তু গুরুত্বপূর্ণ পরিবর্তন হলো সকল সম্ভাব্য পেয়ার traverser করার বদলে আমরা সেগুলো ফর্মুলা দিয়ে হিসাব করব।
উদাহরণ
#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, যা আমাদের প্রাইম পেয়ার সংখ্যা হিসাব করবে।
উপরোক্ত কোডের ব্যাখ্যা
এই কোডে আমরা Sieve of Eratosthenes ব্যবহার করি অ্যারেতে থাকা ম্যাক্স এলিমেন্ট পর্যন্ত সকল প্রাইম সংখ্যা ফ্ল্যাগ করার জন্য। আরেকটি বুল অ্যারেতে আমরা ইনডেক্স-ওয়াইজ এলিমেন্টগুলো প্রাইম কিনা সেটি মার্ক করি।
শেষে আমরা পুরো অ্যারে traverser করি, মোট প্রাইম সংখ্যা বের করি, এবং ফর্মুলা n*(n-1)/2 ব্যবহার করে সকল সম্ভাব্য পেয়ার বের করি। এই ফর্মুলার কারণে আমাদের জটিলতা হয়েছে O(N), যেখানে N হল আমাদের অ্যারের আকার।
উপসংহার
এই আর্টিকেলে আমরা O(n) সময় জটিলতায় একটি অ্যারে-এ প্রাইম পেয়ার সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সমাধানের পূর্ণ পদ্ধতি (সাধারণ এবং দক্ষ) শিখেছি। একই প্রোগ্রাম C, Java, Python বা অন্য ভাষায় লেখা যায়।
