指定した範囲内の素数を生成するホイールふるい（Wheel Sieve）のC++実装プログラム

ホイールふるい（Wheel Sieve）法は、指定された範囲内の素数を見つけるために用いられる手法です。ホイール因数分解（Wheel Factorization）は、エラトステネスのふるいの前処理を手作業で行うための図式的な方法であり、素数と合成数を効率的に分離します。

この手法では、最も内側の円に配置された素数は、外側の各円の同じ相対位置にその倍数を持つことになります。その結果、素数とその倍数が車輪のスポークのように放射状に並びます。内側の円にある素数の倍数は、外側の円において合成数のスポークを形成するのです。

アルゴリズム

開始
    最大値（max number）を定義する
    gen_sieve_primes() を呼び出す
    変数 c を宣言する
    c に 2 を代入する
    p = 2 から最大値まで繰り返す
        もし prime[p] == 0 ならば
            prime[p] = 1
            Mul = p × c
        Mul が最大値未満である間繰り返す
            prime[Mul] = -1
            c を 1 増やす
            Mul = p × c
        繰り返し終了
    繰り返し終了
    print_all_prime() を呼び出す
    c に 0 を代入する
    i = 0 から最大値まで繰り返す
        もし prime[i] == 1 ならば
            c を 1 増やす
    もし c が 4 未満ならば
        Switch(c)
            Case 1
                1番目の素数を出力
            Case 2
                2番目の素数を出力
            Case 3
                3番目の素数を出力
    そうでなければ
        n番目の素数を出力
終了

サンプルコード

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

コードの解説

gen_sieve_prime() 関数では、配列 prime の各要素を走査し、素数には 1 を、合成数には -1 を設定していきます。具体的には、各数値 p についてその倍数（p×2、p×3、…）を順に合成数としてマークする仕組みです。

print_all_prime() 関数では、マークが完了した配列を再度走査し、prime[i] == 1 となっている要素、すなわち素数を順番に出力します。出力時には序数（1st、2nd、3rd、4th…）を付けて表示するようになっています。

出力結果

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