Chương trình C ++ triển khai Sieve of Atkin để tạo các số nguyên tố giữa các dãy đã cho

Đây là chương trình C ++ để thực hiện Sieve of Atkin để tạo các số nguyên tố giữa các dãy đã cho. Sieve of Atkin là một thuật toán hiện đại để tìm tất cả các số nguyên tố cho đến một số nguyên xác định.

Thuật toán

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

Mã mẫu

#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;
}

Đầu ra

2 3 5 7 11 13 17 19 23 29