एराटोस्थनीज की छलनी (Sieve of Eratosthenes) 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 << "अभाज्य संख्याएं जो "<< num <<" से छोटी या बराबर हैं: "; SieveOfEratosthenes(num); return 0; } आउटपुट
उपरोक्त प्रोग्राम का आउटपुट निम्नलिखित है।
15 से छोटी या बराबर अभाज्य संख्याएं: 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 << "अभाज्य संख्याएं जो "<< num <<" से छोटी या बराबर हैं: "; SieveOfEratosthenes(num); return 0; } 
