इस लेख में, हमें कई उपसर्ग योग खोजने की जरूरत है जो सकारात्मक पूर्णांक और श्रेणी क्वेरी L के दिए गए सरणी arr[ ] में अभाज्य संख्याएं हैं। , आर , जहां एल प्रारंभिक अनुक्रमणिका मान arr[ L ] उपसर्ग के लिए है[ ] सरणी और R उपसर्ग योग की संख्या है जिसे हमें खोजने की आवश्यकता है।
उपसर्ग योग सरणी को भरने के लिए, हम अनुक्रमणिका 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 पर मान होगा।
हमें एल से आर तक एक लूप चलाने की जरूरत है जहां एल और आर दिए गए सरणी में संसाधित करने के लिए इंडेक्स की एक श्रृंखला है, फिर प्रीफिक्सम [] सरणी के तत्व की जांच करें और प्रत्येक प्राइम नंबर के लिए गिनती बढ़ाएं।
उदाहरण
#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
उपरोक्त कोड की व्याख्या
इस कोड में, हम एक एरे प्रीफ़िक्ससम [] बना रहे हैं और इसे प्रीफ़िक्ससम [] एरे के पिछले एलिमेंट और दिए गए ऐरे के वर्तमान एलिमेंट के योग से भर रहे हैं। उसके बाद, हम अभाज्य संख्याओं के लिए उपसर्ग सरणियों की सभी संख्याओं की जाँच कर रहे हैं, और यहाँ हम अभाज्य संख्याओं की जाँच के लिए Sieve of Eratosthenes एल्गोरिथम का उपयोग कर रहे हैं। अंत में, प्रत्येक अभाज्य संख्या के लिए गिनती बढ़ाना और परिणाम दिखाना।
निष्कर्ष
इस लेख में, हमने एक भोले दृष्टिकोण को लागू करके और इरेटोस्थनीज की छलनी का उपयोग करके दी गई श्रेणी क्वेरी में कई उपसर्ग योग प्राइम को खोजने का समाधान किया है। उपसर्ग योग सरणी में अभाज्य संख्याएँ खोजने के लिए। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख मददगार लगा होगा।