এরাটোস্থেনিসের ছলনি (Sieve of Eratosthenes) n ছোট প্রাইম নাম্বার খুঁজে বের করার সবচেয়ে দক্ষ পদ্ধতির একটি যখন n প্রায় ১০ মিলিয়ন পর্যন্ত ছোট।
এরাটোস্থেনিসের ছলনি প্রদর্শন করে একটি প্রোগ্রাম নিচে দেওয়া হল।
উদাহরণ
#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() ফাংশন num-এ প্রদত্ত আর্গুমেন্টের আগে যেনে প্রাইম নাম্বারগুলো খুঁজে বের করে। এর কোড স্নিপেট নিচে দেওয়া হল।
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-এর মান সেট করা হয়েছে এবং num-এ ছোট বা সমান সকল প্রাইম নাম্বার প্রিন্ট করা হয়েছে। এটি SieveOfEratosthenes() ফাংশন কল করে করা হয়েছে। এর কোড স্নিপেট নিচে দেওয়া হল।
int main() {
int num = 15;
cout << "The prime numbers smaller or equal to " << num << " are: ";
SieveOfEratosthenes(num);
return 0;
}
