আমাদের একটি পজিটিভ ইন্টিজার অ্যারে দেওয়া আছে। লক্ষ্য হলো এমন সাবঅ্যারে খুঁজে বের করা যাতে প্রতিটি সাবঅ্যারের যোগফল প্রাইম (prime) সংখ্যা হয়। যদি অ্যারে {1,2,3,4} হয়, তবে সাবঅ্যারে: {1,2}, {2,3}, {3,4}। মোট ৩টি।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = {1,3,5,3,2 };
আউটপুট − প্রাইম যোগফল বিশিষ্ট সাবঅ্যারে: ৩
ব্যাখ্যা − সাবঅ্যারে: {3,2} যোগফল=৫ প্রাইম, {3,5,3} যোগফল=১১ প্রাইম, {3,5,3,2} যোগফল=১৩ প্রাইম।
ইনপুট − arr[] = {2,4,6 };
আউটপুট − প্রাইম যোগফল বিশিষ্ট সাবঅ্যারে: ০
ব্যাখ্যা − সব সাবঅ্যারের যোগফল নন-প্রাইম। {2,4}=৬, {4,6}=১০।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
সিভ (sieve) ব্যবহার করে ১০⁷ পর্যন্ত সব প্রাইম সংখ্যা বের করে vector<bool> check-এ স্টোর করব। check[i] = true হলে প্রাইম। এরপর দুটি for লুপ দিয়ে সাবঅ্যারের যোগফল বের করে check[sum] দিয়ে প্রাইম কিনা চেক করব। প্রাইম হলে কাউন্ট বাড়াব।
- অ্যারে
arr[]নিন। sub_prime(int arr[], int size)ফাংশন অ্যারে নিয়ে প্রাইম যোগফল সাবঅ্যারে কাউন্ট রিটার্ন করে।- প্রাথমিক কাউন্ট ০।
temp = pow(10,7)ম্যাক্সিমাম ভ্যালু।vector check(temp+1, true)ইনিশিয়ালাইজ করুন।check[0]এবংcheck[1] = false(নন-প্রাইম)।i=2থেকেi*i <= tempপর্যন্ত সিভ চালান।- এখন
check[i]true হলে প্রাইম। - আরেকবার দুটি লুপে অ্যারে ট্রাভার্স:
total = arr[i]থেকেarr[j]যোগ করুন।check[total]true হলেcount++। countরিটার্ন করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int sub_prime(int arr[], int size) {
int count = 0;
int temp = int(pow(10, 7));
vector<bool> check(temp + 1, true);
check[0] = false;
check[1] = false;
for (int i = 2; i * i <= temp; i++) {
if (check[i] == true) {
for (int j = i * 2; j <= temp; j += i) {
check[j] = false;
}
}
}
for (int i = 0; i < size - 1; ++i) {
int total = arr[i];
for (int j = i + 1; j < size; ++j) {
total += arr[j];
if (check[total]) {
++count;
}
}
}
return count;
}
int main() {
int arr[] = { 3, 5, 1, 9, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of subarrays with Prime sum are: " << sub_prime(arr, size);
return 0;
}
আউটপুট
Count of subarrays with Prime sum are: 1
