এই নিবন্ধে আমরা একটি সাব্যারেতে প্রাইম সংখ্যা খুঁজে বের করার উপায়গুলি বর্ণনা করব। আমাদের কাছে ধনাত্মক সংখ্যার একটি অ্যারে আছে arr[] এবং q প্রশ্নে দুটি পূর্ণসংখ্যা রয়েছে যা আমাদের পরিসীমা {l, R} নির্দেশ করে আমাদের প্রদত্ত পরিসরে প্রাইম সংখ্যা খুঁজে বের করতে হবে। তাই নিচে প্রদত্ত সমস্যার একটি উদাহরণ -
Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3
Output : 2
In the given range the primes are {2, 3}.
Input : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5
Output : 4
In the given range the primes are {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){ // as even number can't be prime so we increment i by 2.
if (N % i == 0)
return false; // if N is divisible by any number then it is not prime.
}
return true;
}
int main(){
int N = 6; // size of array.
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++; // counter variable.
}
cout << cnt << "\n";
}
return 0;
} আউটপুট
2
যাইহোক, এই পদ্ধতিটি খুব ভালো নয় কারণ এই পদ্ধতির সামগ্রিক জটিলতা হল O(Q*N*√N) , যা খুব ভালো নয়।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা একটি বুলিয়ান অ্যারে তৈরি করতে সিভ অফ ইরাটোসথেনেস ব্যবহার করব যা আমাদের বলে যে উপাদানটি প্রাইম কি না, এবং তারপর প্রদত্ত রেঞ্জের মধ্য দিয়ে যান এবং বুল অ্যারে থেকে মোট প্রাইম সংখ্যা খুঁজে বের করব।
উদাহরণ
#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++) {
// If prime[p] is not changed, then
// it is a prime
if (Prime[p] == true) {
// Update all multiples of 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); // boolean array.
int q = 1;
while(q--){
int L = 0, R = 3;
int cnt = 0; // count
for(int i = L; i <= R; i++){
if(isprime[i])
cnt++;
}
cout << cnt << "\n";
}
return 0;
} আউটপুট
2
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিটি ব্রুট ফোর্স পদ্ধতির চেয়ে অনেক দ্রুত যা আমরা আগে প্রয়োগ করেছি কারণ এখন সময়ের জটিলতা হল O(Q*N) যা আগের জটিলতার থেকে অনেক ভালো।
এই পদ্ধতিতে, আমরা উপাদানগুলিকে প্রাক গণনা করি এবং তাদের প্রাইম হিসাবে ফ্ল্যাগ করি বা না; এইভাবে, এটি আমাদের জটিলতা হ্রাস করে। এর উপরে, আমরা Eratosthenes এর Sieve ব্যবহার করছি, যা আমাদের দ্রুত মৌলিক সংখ্যা খুঁজে পেতে সাহায্য করবে। এই পদ্ধতিতে, আমরা O(N*log(log(N)))-এ সমস্ত সংখ্যাকে প্রাইম বা প্রাইম হিসাবে ফ্ল্যাগ করি সংখ্যাগুলিকে তাদের মৌলিক উপাদান ব্যবহার করে ফ্ল্যাগ করে জটিলতা।
উপসংহার
এই নিবন্ধে, আমরা Eratosthenes এর চালনি ব্যবহার করে O(Q*N) এ একটি সাবারেতে প্রাইমগুলির সংখ্যা খুঁজে পেতে একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষায় যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি।
