हमें धनात्मक पूर्णांकों की एक सरणी दी गई है। लक्ष्य सरणी में संख्याओं के उन सबएरे को ढूंढना है जिनमें प्रत्येक सबएरे का योग अभाज्य हो। यदि सरणी {1,2,3,4} है। तो सबएरे होंगे {1,2}, {2,3}, {3,4}। ऐसे सबएरे की संख्या 3 है।
उदाहरण सहित समझ
इनपुट - arr[] = {1,3,5,3,2 };
आउटपुट - अभाज्य योग वाले सबएरे की संख्या: 3
व्याख्या - सबएरे होंगे: {3,2} योग=5 अभाज्य, {3,5,3} योग=11 अभाज्य और {3,5,3,2} योग 13 अभाज्य।
इनपुट - arr[] = {2,4,6 };
आउटपुट - अभाज्य योग वाले सबएरे की संख्या: 0
व्याख्या - सभी सबएरे के गैर-अभाज्य योग हैं। {2,4}=6, {4,6}=10
प्रोग्राम में उपयोग किया गया दृष्टिकोण
हम अधिकतम मान 10^7 से कम सभी अभाज्य संख्याओं को छलनी (sieve) का उपयोग करके ढूंढेंगे और इसे vector<bool> check में संग्रहीत करेंगे। यदि कोई संख्या अभाज्य है तो check[i] सही है अन्यथा गलत। फिर दो फॉर लूप का उपयोग करके सरणी को ट्रैवर्स करें, सबएरे के योग में तत्व जोड़ते रहें और check[sum] का उपयोग करके जांचें कि क्या यह अभाज्य है। यदि हां तो अभाज्य योग वाले सबएरे के लिए काउंट बढ़ाएँ।
- धनात्मक पूर्णांकों की एक सरणी
arr[]लें। - फंक्शन
sub_prime(int arr[], int size)सरणी लेता है और योग अभाज्य होने वाले सबएरे की संख्या लौटाता है। - प्रारंभिक काउंट 0 लें।
temp = pow(10,7)को अधिकतम मान के रूप में आरंभ करें।checkवेक्टर को सही के साथ आरंभ करें।check[0]औरcheck[1]गलत हैं क्योंकि वे गैर-अभाज्य हैं।- i=2 से i*i<=temp तक। सभी संख्याएँ गलत होंगी क्योंकि ये गैर-अभाज्य होंगी।
- अब वेक्टर
check[i]सही है यदि i अभाज्य है अन्यथा गलत। - दो फॉर लूप का उपयोग करके सरणी को फिर से ट्रैवर्स करें।
totalचर को सबएरे में तत्वों के योग के रूप में लें।arr[i]सेarr[j]। जहां i=0 से i<size-1 और j=i+1 से j<size।- यदि कोई
check[total]सही है। (योग कुल अभाज्य है)। काउंट बढ़ाएँ। - सभी लूप के अंत में परिणाम के रूप में काउंट लौटाएँ।
उदाहरण
#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
