【C++】アトキンの篩（Sieve of Atkin）で指定範囲内の素数を生成するプログラム

本記事では、指定された範囲内の素数を生成するために「アトキンの篩（Sieve of Atkin）」を実装したC++プログラムを紹介します。アトキンの篩は、指定した整数までのすべての素数を求めるための現代的なアルゴリズムで、古典的なエラトステネスの篩と比べて理論上はより高速に動作することが知られています。

アルゴリズム

開始
    結果リストを作成し、2・3・5を格納する
    ふるい配列（sieve）をfalseで初期化する
    以下の条件a〜cのいずれかを満たす場合、sieve[n]をtrueにマークする
    a) n = (4*x*x) + (y*y) の解の個数が奇数 かつ n % 12 = 1 または n % 12 = 5
    b) n = (3*x*x) + (y*y) の解の個数が奇数 かつ n % 12 = 7
    c) n = (3*x*x) - (y*y) の解の個数が奇数、x > y かつ n % 12 = 11
    平方数の倍数をすべて非素数としてマークする
    sieve[] を用いて素数を出力する
終了

サンプルコード

#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++) {
            // アトキンの篩の主要部分
            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;
}

実行結果

2 3 5 7 11 13 17 19 23 29

コードのポイント

このプログラムでは、上限値 lmt を30として SieveOfAtkin 関数を呼び出しています。まず2と3を例外的な素数として先に出力し、その後、二次形式ごとの条件に基づいて候補となる数をふるい配列へマークしていきます。マークにはXOR演算（^=）を使用しており、同じ数が偶数回マークされると自動的にフラグが解除される仕組みです。最後に、平方数の倍数をすべて除外することで、正確な素数のリストが得られます。