주어진 범위 사이의 소수를 생성하기 위해 Wheel Sieve를 구현하는 C++ 프로그램

Wheel Sieve 방법은 주어진 범위 사이의 소수를 찾는 데 사용됩니다. 휠 인수분해는 합성에서 소수를 분리하는 에라토스테네스의 체에 대한 예비 작업을 수동으로 수행하기 위한 그래픽 방법입니다.

이 방법에서 가장 안쪽 원의 소수는 다른 원의 자신과 유사한 위치에 배수를 가지며 소수와 그 배수의 스포크를 형성합니다. 가장 안쪽 원에 있는 이러한 소수의 배수는 바깥쪽 원에 있는 합성수의 스포크를 형성합니다.

알고리즘

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