এটি সেগমেন্টেড ছাঁনি (Segmented Sieve) বাস্তবায়ন করে দত্তক পরিসরের মৌলিক সংখ্যা তৈরি করার C++ প্রোগ্রাম। সেগমেন্টেড ছাঁনি প্রথমে সিম্পল ছাঁনি ব্যবহার করে √n পর্যন্ত মৌলিক সংখ্যা বের করে। এই অ্যালগরিদমের মূল ধারণা হল [0 ... n-1] পরিসরকে বিভিন্ন সেগমেন্টে ভাগ করে প্রতিটি সেগমেন্টে মৌলিক সংখ্যা একে একে গণনা করা।
অ্যালগরিদম
শুরু
সিম্পল এরাটোस्थেনিস ছাঁনি ব্যবহার করে লিমিটের চেয়ে ছোট সব মৌলিক সংখ্যা বের করার ফাংশন তৈরি করুন
সেগমেন্টেড ছাঁনি ব্যবহার করে দত্তক পরিসরের সব মৌলিক সংখ্যা বের করুন
A) সিম্পল ছাঁনি ব্যবহার করে high-এর বর্গমূল পর্যন্ত সব মৌলিক সংখ্যা গণনা করুন
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
