โปรแกรม C++ เพื่อใช้ Wheel Sieve เพื่อสร้างหมายเลขเฉพาะระหว่างช่วงที่กำหนด

วิธีตะแกรงล้อใช้เพื่อค้นหาจำนวนเฉพาะระหว่างช่วงที่กำหนด การแยกตัวประกอบของล้อเป็นวิธีการแบบกราฟิกสำหรับดำเนินการเบื้องต้นด้วยตนเองกับตะแกรงของ Eratosthenes ซึ่งแยกจำนวนเฉพาะออกจากคอมโพสิต

ในวิธีนี้ จำนวนเฉพาะในวงกลมวงในสุดจะมีจำนวนทวีคูณในตำแหน่งที่คล้ายคลึงกันในวงกลมอื่นๆ ทำให้เกิดซี่ของจำนวนเฉพาะและทวีคูณ จำนวนเฉพาะจำนวนมากเหล่านี้ในวงกลมชั้นในสุดประกอบเป็นซี่ของจำนวนประกอบในวงกลมรอบนอก

อัลกอริทึม

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

โค้ดตัวอย่าง

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

ผลลัพธ์

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