Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ का उपयोग करके दी गई रेंज क्वेरी में प्रीफिक्स सम अभाज्य संख्याओं की संख्या ज्ञात करें


इस लेख में, हमें दी गई सरणी 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 और अन्य भाषाओं में लिख सकते हैं। आशा है आपको यह लेख उपयोगी लगा होगा।


  1. C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना C++ में स्ट्रिंग के सबस्ट्रिंग्स की संख्या निकालना

    इस लेख में, आप एक दी गई स्ट्रिंग में बनने वाले सबस्ट्रिंग्स (गैर-खाली) की संख्या निकालने के दृष्टिकोण के बारे में जानेंगे।इनपुट: string = moon आउटपुट: 10 व्याख्या: सबस्ट्रिंग्स हैं m, o, o, n, mo, oo, on, moo, oon और moon। इनपुट: string = yellow आउटपुट: 21समाधान खोजने का दृष्टिकोणमान लें स्ट्रिंग की

  1. C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें C++ का उपयोग करके स्टॉपिंग स्टेशनों की संख्या ज्ञात करें

    बिंदु X और Y के बीच n संख्या में इंटरमीडिएट ट्रेन स्टेशन हैं। उन विभिन्न तरीकों की गणना करें जिनसे ट्रेनों को s स्टेशनों पर रुकने के लिए व्यवस्थित किया जा सकता है जैसे कि कोई दो स्टेशन एक-दूसरे के बगल में न हों। तो इस लेख में, हम स्टॉपिंग स्टेशनों की संख्या ज्ञात करने के लिए हर संभव दृष्टिकोण की व्य

  1. C++ का उपयोग करके दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करें C++ का उपयोग करके दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करें

    यूक्लिडियन प्लेन ज्यामिति में एक चतुर्भुज चार शीर्षों और चार किनारों के साथ एक बहुभुज बनाता है। नाम 4-gon आदि। चतुर्भुजों के अन्य नामों में शामिल हैं और कभी-कभी उन्हें वर्ग, डिस्प्ले स्टाइल आदि के रूप में भी जाना जाता है।इस लेख में, हम दिए गए बिंदुओं से संभावित चतुर्भुजों की संख्या ज्ञात करने के दृष