Chương trình C ++ để triển khai Wheel Sieve để tạo số nguyên tố giữa phạm vi đã cho

Phương pháp Wheel Sieve được sử dụng để tìm số nguyên tố giữa một phạm vi nhất định. Phân tích nhân tử bánh xe là một phương pháp đồ họa để thực hiện thủ công một sơ bộ đối với Sàng Eratosthenes để tách các số nguyên tố khỏi các vật liệu tổng hợp.

Trong phương pháp này, các số Nguyên tố ở vòng trong cùng có Bội số của chúng ở vị trí tương tự như chính chúng trong các vòng tròn khác, tạo thành nan hoa của các số nguyên tố và bội số của chúng. Nhiều trong số các số nguyên tố ở vòng trong cùng tạo thành nan hoa của các số tổng hợp ở các vòng ngoài.

Thuật toán

Begin
   Define max number
   gen_sieve_primes()
   Declare c
   Assign c = 2
   For p = 2 to max number
      If prime[p]==0
         prime[p]=1
         Mul = p multiply c
      For Mul less than max number
         prime[Mul] = -1
         Increment c
         Mul = p multiply c
      Done
   Done
   Print_all_prime()
   Assign c=0
   For i = 0 to max number
      if (prime[i] == 1)
         Increment c
   If c less than 4
      Switch(c)
         Case 1
            Print 1st prime number
         Case 2
            Print 2nd prime number
         Case 3
            Print 3rd prime number
   Else
      Print nth prime number
End

Mã mẫu

#include <iostream>
using namespace std;
#define MAX_NUMBER 40
int prime[MAX_NUMBER];
void gen_sieve_prime(void) {
   for (int p = 2; p < MAX_NUMBER; p++) {
      if (prime[p] == 0)
         prime[p] = 1;
         int c = 2;
         int mul = p * c;
      for (; mul < MAX_NUMBER;) {
         prime[mul] = -1;
         c++;
         mul = p * c;
      }
   }
}
void print_all_prime() {
   int c = 0;
   for (int i = 0; i < MAX_NUMBER; i++) {
      if (prime[i] == 1) {
         c++;
         if (c < 4) {
            switch (c) {
               case 1:
                  cout << c << "st prime is: " << i << endl;
                  break;
               case 2:
                  cout << c << "nd prime is: " << i << endl;
                  break;
               case 3:
                  cout << c << "rd prime is: " << i << endl;
                  break;
              default:
              break;
           }
        }else
         cout << c << "th prime is: " << i << endl;
      }
   }
}
int main() {
   gen_sieve_prime();
   print_all_prime();
   return 0;
}

Đầu ra

1st prime is: 2
2nd prime is: 3
3rd prime is: 5
4th prime is: 7
5th prime is: 11
6th prime is: 13
7th prime is: 17
8th prime is: 19
9th prime is: 23
10th prime is: 29
11th prime is: 31
12th prime is: 37