এই নিবন্ধে, আমাদের অনেকগুলি উপসর্গের যোগফল খুঁজে বের করতে হবে যা একটি প্রদত্ত অ্যারে অ্যারে [ ] ধনাত্মক পূর্ণসংখ্যা এবং পরিসরের প্রশ্ন L-এ মৌলিক সংখ্যা। , R , যেখানে L প্রিফিক্সসাম[ ] অ্যারে এবং R এর জন্য প্রাথমিক সূচক মান arr[ L ] উপসর্গ যোগফলের সংখ্যা আমাদের খুঁজে বের করতে হবে।
উপসর্গ সমষ্টি অ্যারে পূরণ করতে, আমরা সূচক L থেকে সূচক R দিয়ে শুরু করি এবং প্রদত্ত অ্যারের শেষ উপাদানের সাথে বর্তমান মান যোগ করি। তাই এখানে সমস্যার উদাহরণ −
Input : arr[ ] = { 3, 5, 6, 2, 4 }
L = 1, R = 3
Output : 3
Explanation : prefixsum[ 0 ] = arr[ L ] = 5
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 2 ] = 11
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 3 ] = 13
In prefixsum[ ] array all three 5, 11 and 13 are prime numbers in prefix sum array in given range.
Input : arr[ ] = { 6, 10, 5, 8, 11 }
L = 0, R = 3
Output : 1
Explanation : prefixsum[ 0 ] = arr[ L ] = 6
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 1 ] = 16
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 2 ] = 21
prefixsum[ 3 ] = prefixsum[ 2 ] + arr[ 3 ] = 29
In prefixsum[ ] array only 29 is the prime number in prefix sum array given range. সমাধান খোঁজার পদ্ধতি
সমস্যাটি দেখে, আমরা বলতে পারি যে আমাদের একটি নতুন অ্যারে প্রিফিক্সসাম তৈরি করতে হবে [ ] এবং প্রিফিক্স যোগ অ্যারের পূর্ববর্তী উপাদান এবং প্রদত্ত অ্যারের বর্তমান উপাদান যোগ করে সেই অ্যারেটি পূরণ করতে হবে। প্রিফিক্স যোগ অ্যারের প্রথম উপাদানটি প্রদত্ত অ্যারের সূচক L-এর মান হবে৷
আমাদের L থেকে R পর্যন্ত একটি লুপ চালাতে হবে যেখানে L এবং R প্রদত্ত অ্যারেতে প্রক্রিয়া করার জন্য সূচকগুলির একটি পরিসর, তারপর উপসর্গের উপাদানটি পরীক্ষা করুন [ ] অ্যারের এবং পাওয়া প্রতিটি মৌলিক সংখ্যার জন্য গণনা বৃদ্ধি করুন৷
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
vector < bool > checkprime (int *arr, int n, int MAX){
vector < bool > p (n);
bool Prime_val[MAX + 1];
for (int i = 2; i < MAX; i++)
Prime_val[i] = true;
Prime_val[1] = false;
for (int p = 2; p * p <= MAX; p++){
// If prime[p] is not changed, then
// it is a prime
if (Prime_val[p] == true){
// Update all multiples of p
for (int i = p * 2; i <= MAX; i += p)
Prime_val[i] = false;
}
}
for (int i = 0; i < n; i++){
if (Prime_val[arr[i]])
p[i] = true;
else
p[i] = false;
}
return p;
}
int main (){
int arr[] = { 2, 3, 4, 7, 9, 10 };
int s1 = sizeof (arr) / sizeof (arr[0]);//size of given array
int L = 1, R = 3, s2 = R - L + 1;
int prefixsum[s2];
int count = 0;
prefixsum[0] = arr[L];
for (int i = L + 1, j = 1; i <= R && j < s1; i++, j++){
prefixsum[j] = prefixsum[j - 1] + arr[i];
}
vector < bool > isprime = checkprime (prefixsum, s2, prefixsum[s2 - 1]);
for (int i = 0; i < s2; i++) {
if (isprime[i] == 1)
count++;
}
cout <<"Number of prefix sum prime in given range query: " << count;
return 0;
} আউটপুট
Number of prefix sum prime in given range query: 2
উপরের কোডের ব্যাখ্যা
এই কোডটিতে, আমরা একটি অ্যারে প্রিফিক্সসাম[ ] তৈরি করছি এবং প্রিফিক্সসাম[ ] অ্যারের আগের উপাদান এবং প্রদত্ত অ্যারের বর্তমান উপাদানের যোগফল দিয়ে এটি পূরণ করছি। এর পরে, আমরা মৌলিক সংখ্যার জন্য উপসর্গ অ্যারেগুলির সমস্ত সংখ্যা পরীক্ষা করছি, এবং এখানে আমরা মৌলিক সংখ্যাগুলি পরীক্ষা করার জন্য ইরাটোস্থেনিস অ্যালগরিদম ব্যবহার করছি। অবশেষে, প্রতিটি মৌলিক সংখ্যার জন্য গণনা বৃদ্ধি করা এবং ফলাফল দেখানো।
উপসংহার
এই নিবন্ধে, আমরা একটি নিরীহ পদ্ধতি প্রয়োগ করে এবং Eratosthenes এর চালনি ব্যবহার করে একটি প্রদত্ত পরিসরের ক্যোয়ারীতে অনেকগুলি উপসর্গ যোগ প্রাইম খুঁজে বের করার সমাধান করেছি। উপসর্গ সমষ্টি অ্যারেতে মৌলিক সংখ্যা খুঁজে বের করতে। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আশা করি আপনি এই নিবন্ধটি সহায়ক বলে মনে করেন৷
