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

C++ का उपयोग करके सबअर्रे में अभाज्य संख्याओं की संख्या ज्ञात करें


इस लेख में हम सबअर्रे में अभाज्य संख्याओं की संख्या ज्ञात करने के तरीकों का वर्णन करेंगे। हमारे पास धनात्मक संख्याओं की एक सरणी arr[] है और q क्वेरीज हैं जिनमें दो पूर्णांक हैं जो हमारी रेंज {l, R} को दर्शाते हैं, हमें दी गई रेंज में अभाज्य संख्याओं की संख्या ढूंढनी है। तो नीचे दी गई समस्या का एक उदाहरण है:

Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3 Output : 2 दी गई रेंज में अभाज्य संख्याएं हैं {2, 3}। Input : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5 Output : 4 दी गई रेंज में अभाज्य संख्याएं हैं {2, 3, 5, 11}।

समाधान खोजने का दृष्टिकोण

इस स्थिति में, दो दृष्टिकोण दिमाग में आते हैं:

ब्रूट फोर्स

इस दृष्टिकोण में, हम रेंज ले सकते हैं और उस रेंज में मौजूद अभाज्य संख्याओं की संख्या ढूंढ सकते हैं।

उदाहरण

#include <bits/stdc++.h> using namespace std; bool isPrime(int N){     if (N <= 1)         return false;     if (N <= 3)         return true;     if(N % 2 == 0 || N % 3 == 0)         return false;     for (int i = 5; i * i <= N; i = i + 2){ // क्योंकि सम संख्या अभाज्य नहीं हो सकती इसलिए हम i को 2 से बढ़ाते हैं         if (N % i == 0)             return false; // यदि N किसी संख्या से विभाज्य है तो यह अभाज्य नहीं है     }     return true; } int main(){     int N = 6; // सरणी का आकार     int arr[N] = {1, 2, 3, 4, 5, 6};     int Q = 1;     while(Q--){         int L = 0, R = 3;         int cnt = 0;         for(int i = L; i <= R; i++){             if(isPrime(arr[i]))                 cnt++; // काउंटर चर         }         cout << cnt << "\n";     }     return 0; }

आउटपुट

2

हालांकि, यह दृष्टिकोण बहुत अच्छा नहीं है क्योंकि इस दृष्टिकोण की समग्र जटिलता O(Q*N*√N) है, जो बहुत अच्छी नहीं है।

कुशल दृष्टिकोण

इस दृष्टिकोण में, हम एराटोस्थनीज की छलनी का उपयोग करके एक बूलियन सरणी बनाएंगे जो हमें बताती है कि तत्व अभाज्य है या नहीं, और फिर दी गई रेंज के माध्यम से जाएंगे और बूल सरणी से अभाज्य संख्याओं की कुल संख्या ढूंढेंगे।

उदाहरण

#include <bits/stdc++.h> using namespace std; vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){     vector<bool> p(n);     bool Prime[MAX + 1];     for(int i = 2; i < MAX; i++)         Prime[i] = true;     Prime[1] = false;     for (int p = 2; p * p <= MAX; p++) {         // यदि prime[p] बदला नहीं गया है, तो         // यह एक अभाज्य संख्या है         if (Prime[p] == true) {             // p के सभी गुणकों को अपडेट करें             for (int i = p * 2; i <= MAX; i += p)                 Prime[i] = false;         }     }     for(int i = 0; i < n; i++){         if(Prime[arr[i]])             p[i] = true;         else             p[i] = false;     }     return p; } int main(){     int n = 6;     int arr[n] = {1, 2, 3, 4, 5, 6};     int MAX = -1;     for(int i = 0; i < n; i++){         MAX = max(MAX, arr[i]);     }     vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // बूलियन सरणी     int q = 1;     while(q--){         int L = 0, R = 3;         int cnt = 0; // काउंट         for(int i = L; i <= R; i++){             if(isprime[i])                 cnt++;         }         cout << cnt << "\n";     }     return 0; }

आउटपुट

2

उपरोक्त कोड की व्याख्या

यह दृष्टिकोण पहले लागू किए गए ब्रूट फोर्स दृष्टिकोण की तुलना में बहुत तेज़ है क्योंकि अब समय जटिलता O(Q*N) है जो पिछली जटिलता से बहुत बेहतर है।

इस दृष्टिकोण में, हम तत्वों को पूर्व-गणना करते हैं और उन्हें अभाज्य या नहीं के रूप में फ्लैग करते हैं; इस प्रकार, यह हमारी जटिलता को कम करता है। इसके अलावा, हम एराटोस्थनीज की छलनी का भी उपयोग कर रहे हैं, जो हमें अभाज्य संख्याओं को तेजी से ढूंढने में मदद करेगा। इस विधि में, हम अपने अभाज्य गुणनखंडों का उपयोग करके संख्याओं को O(N*log(log(N))) जटिलता में अभाज्य या गैर-अभाज्य के रूप में फ्लैग करते हैं।

निष्कर्ष

इस लेख में, हम एराटोस्थनीज की छलनी का उपयोग करके O(Q*N) में सबअर्रे में अभाज्य संख्याओं की संख्या ज्ञात करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य और कुशल) भी सीखा जिससे हमने इस समस्या को हल किया। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं।


  1. C++ का उपयोग करके पेंटागोनल पिरामिडल संख्या ज्ञात करना C++ का उपयोग करके पेंटागोनल पिरामिडल संख्या ज्ञात करना

    एक पेंटागोनल पिरामिडल संख्या पेंटागोनल बेस पिरामिड में वस्तुओं की संख्या के बराबर होती है। नीचे कुछ पेंटागोनल संख्याएं देखें। N तक पेंटागोनल संख्याओं का योग Nवीं पेंटागोनल पिरामिडल संख्या के बराबर होता है। इस लेख में, हम Nवीं पेंटागोनल पिरामिडल संख्या खोजने पर चर्चा करेंगे, उदाहरण के लिए: इनपुट:

  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 स्टेशनों पर रुकने के लिए व्यवस्थित किया जा सकता है जैसे कि कोई दो स्टेशन एक-दूसरे के बगल में न हों। तो इस लेख में, हम स्टॉपिंग स्टेशनों की संख्या ज्ञात करने के लिए हर संभव दृष्टिकोण की व्य