এই আর্টিকেলে আমরা একটি সাবঅ্যারে-এ প্রাইম সংখ্যা গণনা করার উপায় বর্ণনা করব। আমাদের কাছে একটি ধনাত্মক সংখ্যার অ্যারে arr[] এবং q কোয়েরি আছে যেকোনো দুটি পূর্ণসংখ্যা দিয়ে আমাদের রেঞ্জ {L, R} বোঝায়। আমাদের কাজ হল দেওয়া রেঞ্জে কতটি প্রাইম সংখ্যা আছে সেটি বের করা। নিচে উদাহরণ:
ইনপুট : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3
আউটপুট : 2
দেওয়া রেঞ্জে প্রাইমগুলো হল {2, 3}।
ইনপুট : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5
আউটপুট : 4
দেওয়া রেঞ্জে প্রাইমগুলো হল {2, 3, 5, 11}।
সমাধানের পদ্ধতি
এই পরিস্থিতিতে দুটি পদ্ধতি মনে হয়:
ব্রুট ফোর্স
এই পদ্ধতিতে আমরা রেঞ্জ নিয়ে সেই রেঞ্জে কতটি প্রাইম আছে সেটি বের করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; bool isPrime(int N){ if (N <= 1) return false; if (N <= 3) return true; if(N % 2 == 0 || N % 3 == 0) return false; for (int i = 5; i * i <= N; i = i + 2){ // জোড় সংখ্যা প্রাইম হতে পারে না তাই i ২ বাড়াচ্ছি if (N % i == 0) return false; // যদি N যেকোনো সংখ্যা দিয়ে বিভাজ্য হয় তবে প্রাইম নয় } return true; } int main(){ int N = 6; // অ্যারের আকার int arr[N] = {1, 2, 3, 4, 5, 6}; int Q = 1; while(Q--){ int L = 0, R = 3; int cnt = 0; for(int i = L; i <= R; i++){ if(isPrime(arr[i])) cnt++; // কাউন্টার ভেরিয়েবল } cout << cnt << "\n"; } return 0; }
আউটপুট
2
তবে এই পদ্ধতিটি ভালো নয় কারণ এর সমগ্র জটিলতা O(Q*N*√N), যা ভালো নয়।
দক্ষ পদ্ধতি (Efficient Approach)
এই পদ্ধতিতে আমরা Sieve Of Eratosthenes ব্যবহার করে একটি বুলিয়ান অ্যারে বানাবো যা বলবে উপাদানটি প্রাইম কিনা, এবং তারপর দেওয়া রেঞ্জ traverser করে বুলিয়ান অ্যারে থেকে মোট প্রাইম সংখ্যা বের করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){ vector<bool> p(n); bool Prime[MAX + 1]; for(int i = 2; i < MAX; i++) Prime[i] = true; Prime[1] = false; for (int p = 2; p * p <= MAX; p++) { // যদি Prime[p] পরিবর্তন না হয়, তবে // সেটি একটি প্রাইম if (Prime[p] == true) { // p-এর সকল মাল্টিপল আপডেট for (int i = p * 2; i <= MAX; i += p) Prime[i] = false; } } for(int i = 0; i < n; i++){ if(Prime[arr[i]]) p[i] = true; else p[i] = false; } return p; } int main(){ int n = 6; int arr[n] = {1, 2, 3, 4, 5, 6}; int MAX = -1; for(int i = 0; i < n; i++){ MAX = max(MAX, arr[i]); } vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // বুলিয়ান অ্যারে int q = 1; while(q--){ int L = 0, R = 3; int cnt = 0; // কাউন্ট for(int i = L; i <= R; i++){ if(isprime[i]) cnt++; } cout << cnt << "\n"; } return 0; }
আউটপুট
2
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতি ব্রুট ফোর্স পদ্ধতির চেয়ে অনেক দ্রুত কারণ এখন সময় জটিলতা O(Q*N) যা আগের জটিলতার চেয়ে ভালো।
এই পদ্ধতিতে আমরা előre উপাদানগুলো প্রিক্যালকুলেট করে প্রাইম কিনা ফ্ল্যাগ করি, এতে জটিলতা কমে।その上 আমরা Sieve Of Eratosthenes ব্যবহার করছি যা প্রাইম সংখ্যা দ্রুত বের করতে সাহায্য করে। এই মেথডে আমরা সকল সংখ্যাকে তাদের প্রাইম ফ্যাক্টর ব্যবহার করে প্রাইম বা নন-প্রাইম ফ্ল্যাগ করি O(N*log(log(N))) জটিলতায়।
উপসংহার
এই আর্টিকেলে আমরা Sieve Of Eratosthenes ব্যবহার করে O(Q*N) সময় জটিলতায় সাবঅ্যারে-এ প্রাইম সংখ্যা বের করার সমস্যা সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সমাধানের পূর্ণ পদ্ধতি (সাধারণ এবং দক্ষ) শিখেছি। একই প্রোগ্রাম C, Java, Python বা অন্য ভাষায় লেখা যায়।
