यह दिए गए रेंज के बीच प्राइम नंबर जेनरेट करने के लिए सेगमेंटेड चलनी को लागू करने के लिए सी ++ प्रोग्राम है। खंडित चलनी पहले (n) से छोटे या उसके बराबर अभाज्य संख्याओं को खोजने के लिए साधारण चलनी का उपयोग करती है। इस एल्गोरिथम का विचार श्रेणी [0 ... n-1] को अलग-अलग खंडों में विभाजित करना और सभी खंडों में एक-एक करके अभाज्य संख्याओं की गणना करना है।
एल्गोरिदम
Begin Create function to find all primes smaller than limit using simple sieve of eratosthenes. Finds all prime numbers in given range using segmented sieve A) Compute all primes smaller or equal to square root of high using simple sieve B) Count of elements in given range C) Declaring boolean only for [low, high] D) Find the minimum number in [low ... high] that is a multiple of prime[i] (divisible by prime[i]) E) Mark multiples of prime[i] in [low … high] F) Numbers which are not marked in range, are prime End
उदाहरण कोड
#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