इराटोस्थनीज की चलनी 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 << " ";
} फ़ंक्शन मुख्य () संख्या का मान सेट करता है और फिर उन सभी अभाज्य संख्याओं को प्रिंट करता है जो संख्या से छोटी या बराबर होती हैं। यह फ़ंक्शन SieveOfEratosthenes() को कॉल करके किया जाता है। इसके लिए कोड स्निपेट इस प्रकार दिया गया है।
int main() {
int num = 15;
cout << "The prime numbers smaller or equal to "<< num <<" are: ";
SieveOfEratosthenes(num);
return 0;
}