এই আর্টিকেলে আমাদের কাজ হল একটি ধনাত্মক পূর্ণসংখ্যার অ্যারে arr[ ] এবং রেঞ্জ কোয়েরি L, R দেওয়ায় প্রিফিক্স সম (prefix sum) এর মধ্যে কতটি প্রাইম সংখ্যা আছে সেটি বের করা, যেখানে L হল প্রিফিক্স সম অ্যারেতে arr[L] ইনডেক্স থেকে শুরু হবে এবং R হল কতগুলো প্রিফিক্স সম বের করতে হবে।
প্রিফিক্স সম অ্যারে বানাতে আমরা ইনডেক্স L থেকে R পর্যন্ত চলব এবং প্রদত্ত অ্যারেতে বর্তমান মানটি প্রিফিক্স সম অ্যারেতে শেষ এলিমেন্টের সাথে যোগ করব। প্রিফিক্স সম অ্যারেতে প্রথম এলিমেন্ট হবে দেওয়া অ্যারেতে ইনডেক্স L-এ থাকা মান। উদাহরণ:
ইনপুট : arr[ ] = { 3, 5, 6, 2, 4 } L = 1, R = 3
আউটপুট : 3
ব্যাখ্যা : prefixsum[ 0 ] = arr[ L ] = 5
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 2 ] = 11
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 3 ] = 13
প্রিফিক্স সম অ্যারেতে সব তিনটি 5, 11 এবং 13 প্রাইম সংখ্যা দেওয়া রেঞ্জে।
ইনপুট : arr[ ] = { 6, 10, 5, 8, 11 } L = 0, R = 3
আউটপুট : 1
ব্যাখ্যা : 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
প্রিফিক্স সম অ্যারেতে শুধু 29 প্রাইম সংখ্যা দেওয়া রেঞ্জে।
সমাধানের পদ্ধতি
সমস্যাটি দেখে বলা যায়, আমাদের একটি নতুন অ্যারে prefixsum[ ] বানাতে হবে এবং সেটিকে দেওয়া অ্যারেতে বর্তমান এলিমেন্ট এবং প্রিফিক্স সম অ্যারেতে পূর্ববর্তী এলিমেন্ট যোগ করে পূরণ করতে হবে। প্রিফিক্স সম অ্যারেতে প্রথম এলিমেন্ট হবে দেওয়া অ্যারেতে ইনডেক্স L-এ থাকা মান।
আমাদের L থেকে R পর্যন্ত লুপ চালাতে হবে যেখানে L এবং R দেওয়া অ্যারেতে প্রসেস করার ইনডেক্স রেঞ্জ, তারপর prefixsum[ ] অ্যারেতে এলিমেন্ট চেক করি এবং প্রতিটি প্রাইম সংখ্যা পাওয়ার জন্য কাউন্ট বাড়াই।
উদাহরণ
#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]);//দেওয়া অ্যারের আকার 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
উপরোক্ত কোডের ব্যাখ্যা
এই কোডে আমরা একটি prefixsum[ ] অ্যারে বানাই এবং সেটিকে প্রিফিক্স সম অ্যারেতে পূর্ববর্তী এলিমেন্ট এবং দেওয়া অ্যারেতে বর্তমান এলিমেন্ট যোগ করে পূরণ করি। এরপর প্রিফিক্স অ্যারেতে সকল সংখ্যা প্রাইম কিনা চেক করি, এবং এখানে আমরা Sieve of Eratosthenes অ্যালগরিদম ব্যবহার করি প্রাইম চেক করার জন্য। অবশেষে প্রতিটি প্রাইম সংখ্যা পাওয়ার জন্য কাউন্ট বাড়িয়ে ফলাফল দেখাই।
উপসংহার
এই আর্টিকেলে আমরা Sieve of Eratosthenes ব্যবহার করে প্রদত্ত রেঞ্জ কোয়েরিতে প্রিফিক্স সম প্রাইম সংখ্যা বের করার সমস্যা সমাধান করেছি। একই প্রোগ্রাম C, Java, Python বা অন্য ভাষায় লেখা যায়। আশা করি এই আর্টিকেলটি সহায়ক হবে।
