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

C++ प्रोग्राम: सेगमेंटेड छलनी द्वारा दी गई सीमा में अभाज्य संख्याएं उत्पन्न करना


यह दी गई सीमा में अभाज्य संख्याएं उत्पन्न करने के लिए सेगमेंटेड छलनी को लागू करने वाला C++ प्रोग्राम है। सेगमेंटेड छलनी पहले सरल छलनी का उपयोग करके √n से छोटी या बराबर अभाज्य संख्याएं ढूंढती है। इस एल्गोरिदम का विचार रेंज [0 ... n-1] को विभिन्न सेगमेंट में विभाजित करना और एक-एक करके सभी सेगमेंट में अभाज्य संख्याओं की गणना करना है।

एल्गोरिदम

शुरुआत    सरल एराटोस्थनीज छलनी का उपयोग करके सीमा से छोटे सभी अभाज्य संख्याओं को खोजने के लिए फंक्शन बनाएं    सेगमेंटेड छलनी का उपयोग करके दी गई सीमा में सभी अभाज्य संख्याएं खोजें    A) सरल छलनी का उपयोग करके उच्च के वर्गमूल से छोटी या बराबर सभी अभाज्य संख्याओं की गणना करें    B) दी गई सीमा में तत्वों की संख्या    C) केवल [low, high] के लिए बूलियन घोषित करें    D) [low ... high] में वह न्यूनतम संख्या ढूंढें जो prime[i] का गुणक है (prime[i] से विभाज्य) E) [low ... high] में prime[i] के गुणकों को चिह्नित करें F) सीमा में जो संख्याएं चिह्नित नहीं हैं, वे अभाज्य हैं अंत

उदाहरण कोड

#include <bits/stdc++.h> using namespace std; void simpleSieve(int lmt, vector<int>& prime) {    bool mark[lmt + 1];    memset(mark, false, sizeof(mark));    for (int i = 2; i <= lmt; ++i) {       if (mark[i] == false) {          prime.push_back(i);          for (int j = i; j <= lmt; j += i)             mark[j] = true;       }    } } void PrimeInRange(int low, int high) {    int lmt = floor(sqrt(high)) + 1;    vector<int> prime;    simpleSieve(lmt, prime);    int n = high - low + 1;    bool mark[n + 1];    memset(mark, false, sizeof(mark));    for (int i = 0; i < prime.size(); i++) {       int lowLim = floor(low / prime[i]) * prime[i];       if (lowLim < low)          lowLim += prime[i];       for (int j = lowLim; j <= high; j += prime[i])          mark[j - low] = true;    }    for (int i = low; i <= high; i++)       if (!mark[i - low])          cout << i << " "; } int main() { int low = 10, high = 50; PrimeInRange(low, high); return 0; }

आउटपुट

11 13 17 19 23 29 31 37 41 43 47

  1. - C++ प्रोग्राम: एराटोस्थनीज की छलनी द्वारा दी गई सीमा में अभाज्य संख्याएं उत्पन्न करना

    यह दी गई सीमा में अभाज्य संख्याएं उत्पन्न करने के लिए एराटोस्थनीज की छलनी को लागू करने वाला C++ प्रोग्राम है। इस विधि में, एक पूर्णांक सरणी जिसके सभी तत्व शून्य से आरंभ होते हैं। यह वहां अनुसरण करता है जहां प्रत्येक गैर-अभाज्य तत्व का सूचकांक नेस्टेड लूप के अंदर 1 के रूप में चिह्नित होता है। अभाज्य

  1. - C++ प्रोग्राम: व्हील छलनी द्वारा दी गई सीमा में अभाज्य संख्याएं उत्पन्न करना

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

  1. - C++ में दो अंतराल के बीच अभाज्य संख्याएं प्रदर्शित करने का प्रोग्राम

    एक अभाज्य संख्या एक पूर्ण संख्या है जो एक से बड़ी होती है और अभाज्य संख्या के केवल कारक एक और स्वयं होने चाहिए। कुछ पहली अभाज्य संख्याएँ 2, 3, 5, 7, 11, 13, 17 आदि हैं। दो अंतराल के बीच कई अभाज्य संख्याएँ हो सकती हैं। उदाहरण के लिए, अंतराल 5 और 20 के बीच अभाज्य संख्याएँ हैं: 5, 7, 11, 13, 17 और 19।