প্রদত্ত পরিসরের মধ্যে প্রাইম নম্বর তৈরি করতে অ্যাটকিনের চালনি বাস্তবায়নের জন্য C++ প্রোগ্রাম

দেওয়া রেঞ্জের মধ্যে প্রাইম নম্বর তৈরি করতে সিভ অফ অ্যাটকিন বাস্তবায়নের জন্য এটি 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