सी ++ प्रोग्राम दिए गए रेंज के बीच प्राइम नंबर उत्पन्न करने के लिए एटकिन की चलनी को लागू करने के लिए

यह दिए गए रेंज के बीच प्राइम नंबर जेनरेट करने के लिए Sieve of Atkin को लागू करने के लिए C++ प्रोग्राम है। एटकिन की चलनी एक निर्दिष्ट पूर्णांक तक सभी अभाज्य संख्याओं को खोजने के लिए एक आधुनिक एल्गोरिथम है।

एल्गोरिदम

Begin
   Create a results list, filled with 2, 3, and 5.
   Initialize the sieve array with false values
   Mark siev[n] is true if one of the following is true:
   a) n = (4*x*x) + (y*y) has odd number of solutions
      n % 12 = 1 or n % 12 = 5.
   b) n = (3*x*x) + (y*y) has odd number of solutions and n % 12 = 7
   c) n = (3*x*x) - (y*y) has odd number of solutions, x > y and n % 12 = 11
   Mark all multiples of squares as non-prime
   Print primes using sieve[]
End

उदाहरण कोड

#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++) {
         // Main part of Sieve of Atkin
         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