यह दी गई सीमा में अभाज्य संख्याएं उत्पन्न करने के लिए सेगमेंटेड छलनी को लागू करने वाला 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