यह दी गई सीमा में अभाज्य संख्याएं उत्पन्न करने के लिए एटकिन की छलनी को लागू करने वाला C++ प्रोग्राम है। एटकिन की छलनी एक निर्दिष्ट पूर्णांक तक सभी अभाज्य संख्याएं खोजने के लिए एक आधुनिक एल्गोरिदम है।
एल्गोरिदम
शुरुआत एक परिणाम सूची बनाएं, जो 2, 3, और 5 से भरी हो। छलनी सरणी को गलत मानों से आरंभ करें siev[n] को सच चिह्नित करें यदि निम्न में से कोई सत्य है: a) n = (4*x*x) + (y*y) के विषम संख्या में समाधान हैं n % 12 = 1 या n % 12 = 5। b) n = (3*x*x) + (y*y) के विषम संख्या में समाधान हैं और n % 12 = 7 c) n = (3*x*x) - (y*y) के विषम संख्या में समाधान हैं, x > y और n % 12 = 11 वर्गों के सभी गुणकों को गैर-अभाज्य के रूप में चिह्नित करें छलनी[] का उपयोग करके अभाज्य संख्याएं प्रिंट करें अंत
उदाहरण कोड
#include <bits/stdc++.h> using namespace std; int SieveOfAtkin(int lmt) { if (lmt > 2) cout << 2 << " "; if (lmt > 3) cout << 3 << " "; bool sieve[lmt]; for (int i = 0; i < lmt; i++) sieve[i] = false; for (int a = 1; a * a < lmt; a++) { for (int b = 1; b * b < lmt; b++) { // एटकिन की छलनी का मुख्य भाग int n = (4 * a* a) + (b * b); if (n <= lmt && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true; n = (3 * a * a) + (b * b); if (n <= lmt && n % 12 == 7) sieve[n] ^= true; n = (3 * a * a) - (b * b); if (a > b && n <= lmt && n % 12 == 11) sieve[n] ^= true; } } for (int r = 5; r * r < lmt; r++) { if (sieve[r]) { for (int i = r * r; i < lmt; i += r * r) sieve[i] = false; } } for (int x = 5; x < lmt; x++) if (sieve[x]) cout << x << " "; } int main(void) { int lmt = 30; SieveOfAtkin(lmt); return 0; }
आउटपुट
2 3 5 7 11 13 17 19 23 29