इस लेख में, हमें दी गई सरणी arr[] में प्रीफिक्स सम की संख्या ढूंढनी है जो अभाज्य संख्याएं हैं और रेंज क्वेरी L, R, जहां L प्रीफिक्ससम[] सरणी के लिए प्रारंभिक इंडेक्स मान 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 प्रीफिक्ससम[] सरणी में दी गई रेंज में सभी तीन 5, 11 और 13 अभाज्य संख्याएं हैं। 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 प्रीफिक्ससम[] सरणी में दी गई रेंज में केवल 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++){ // यदि prime[p] नहीं बदला गया है, तो // यह एक अभाज्य संख्या है if (Prime_val[p] == true){ // 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 <<"दी गई रेंज क्वेरी में प्रीफिक्स सम अभाज्य की संख्या: " << count; return 0; }आउटपुट
दी गई रेंज क्वेरी में प्रीफिक्स सम अभाज्य की संख्या: 2
उपरोक्त कोड की व्याख्या
इस कोड में, हम एक सरणी prefixsum[] बना रहे हैं और इसे prefixsum[] सरणी के पिछले तत्व और दी गई सरणी के वर्तमान तत्व के योग से भर रहे हैं। उसके बाद, हम प्रीफिक्स सरणी की सभी संख्याओं की अभाज्य संख्याओं के लिए जांच कर रहे हैं, और यहां हम अभाज्य संख्याओं की जांच के लिए एराटोस्थनीज की छलनी एल्गोरिदम का उपयोग कर रहे हैं। अंत में, प्रत्येक अभाज्य संख्या के लिए काउंट बढ़ा रहे हैं और परिणाम दिखा रहे हैं।
निष्कर्ष
इस लेख में, हमने नैव दृष्टिकोण लागू करके और प्रीफिक्स सम सरणी में अभाज्य संख्याओं को ढूंढने के लिए एराटोस्थनीज की छलनी का उपयोग करके दी गई रेंज क्वेरी में प्रीफिक्स सम अभाज्य की संख्या ज्ञात करने की समस्या को हल किया। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।