এরাটোসথেনেসের চালনি হল n-এর থেকে ছোট মৌলিক সংখ্যাগুলি খুঁজে বের করার সবচেয়ে কার্যকর উপায়গুলির মধ্যে একটি যখন n প্রায় 10 মিলিয়নের চেয়ে ছোট।
একটি প্রোগ্রাম যা ইরাটোসথেনিসের চালনী প্রদর্শন করে তা নিম্নরূপ দেওয়া হল।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int num) {
bool pno[num+1];
memset(pno, true, sizeof(pno));
for (int i = 2; i*i< = num; i++) {
if (pno[i] == true) {
for (int j = i*2; j< = num; j + = i)
pno[j] = false;
}
}
for (int i = 2; i< = num; i++)
if (pno[i])
cout << i << " ";
}
int main() {
int num = 15;
cout << "The prime numbers smaller or equal to "<< num <<" are: ";
SieveOfEratosthenes(num);
return 0;
} আউটপুট
উপরের প্রোগ্রামের আউটপুট নিম্নরূপ।
The prime numbers smaller or equal to 15 are: 2 3 5 7 11 13
এখন, আসুন আমরা উপরের প্রোগ্রামটি বুঝতে পারি।
SieveOfEratosthenes() ফাংশনটি আর্গুমেন্ট হিসাবে দেওয়া সংখ্যার আগে হওয়া সমস্ত মৌলিক সংখ্যা খুঁজে পায়। এর জন্য কোড স্নিপেট নিম্নরূপ দেওয়া হয়েছে।
void SieveOfEratosthenes(int num) {
bool pno[num+1];
memset(pno, true, sizeof(pno));
for (int i = 2; i*i< = num; i++) {
if (pno[i] == true) {
for (int j = i*2; j< = num; j + = i)
pno[j] = false;
}
}
for (int i = 2; i< = num; i++)
if (pno[i])
cout << i << " ";
} ফাংশন main() num-এর মান নির্ধারণ করে এবং তারপর সংখ্যার সমান বা ছোট সমস্ত মৌলিক সংখ্যা প্রিন্ট করে। এটি ফাংশন SieveOfEratosthenes() কল করে করা হয়। এর জন্য কোড স্নিপেট নিম্নরূপ দেওয়া হয়েছে।
int main() {
int num = 15;
cout << "The prime numbers smaller or equal to "<< num <<" are: ";
SieveOfEratosthenes(num);
return 0;
} 