サンダラムのふるい（Sieve of Sundaram）で指定範囲内の素数を生成するC++プログラム

本記事では、サンダラムのふるい（Sieve of Sundaram）を実装し、指定した範囲までの素数を生成するC++プログラムを紹介します。サンダラムのふるいは、1934年にインドの数学者S.P.サンダラムによって発見された素数生成アルゴリズムです。

サンダラムのふるいとは

サンダラムのふるいは、エラトステネスのふるいと同様に素数を求めるアルゴリズムですが、奇数のみを扱うことで効率化を図っています。n未満の素数を求める際は、まず (n−2)/2 のサイズの配列を用意し、「i + j + 2ij」（1 ≤ i ≤ j）の形で表される数値を順にマークしていきます。最終的にマークされていないインデックス i に対して「2i + 1」を出力すれば、それがそのまま素数となります。

アルゴリズムの手順

Begin
   printPrimes(n)
   n未満の素数を求めるため、n−2 を半分にした値を New とする。
   New = (n−2)/2;
   「i + j + 2ij」（1 ≤ i ≤ j）の形の数を区別するための配列 marked[n] を作成する。
   marked[] のすべての要素を false で初期化する。
   条件を満たすすべての i + j + 2ij を true としてマークする。
   for i = 1 to New
      a) j = i;
      b) (i + j + 2×i×j) ≤ New の間、j を増やしながら該当要素を true にする。
   m > 2 の場合は、最初の素数として 2 を出力する。
   残りの素数は 2i + 1 の形で表されるため、
   marked[i] が false となるすべての i について 2i + 1 を出力する。
End

サンプルコード

#include <bits/stdc++.h>
using namespace std;

int SieveOfSundaram(int m) {
    int N = (m - 2) / 2;
    bool marked[N + 1];
    memset(marked, false, sizeof(marked));

    // i + j + 2ij の形の数をマーク
    for (int i = 1; i <= N; i++)
        for (int j = i; (i + j + 2 * i * j) <= N; j++)
            marked[i + j + 2 * i * j] = true;

    // 2 は唯一の偶数の素数
    if (m > 2)
        cout << 2 << " ";

    // マークされていないインデックスから素数を出力
    for (int i = 1; i <= N; i++)
        if (marked[i] == false)
            cout << 2 * i + 1 << " ";
}

int main(void) {
    int m = 10;
    SieveOfSundaram(m);
    return 0;
}

実行結果

2 3 5 7

コードの解説

このプログラムでは m = 10 として実行しています。まず N = (10 − 2) / 2 = 4 が計算され、サイズ 5 の boolean 配列 marked が用意されます。二重ループにより「i + j + 2ij」の形の数値がマークされ、最後にマークされていないインデックス 1・2・3 に対応する 3、5、7 と、最初の素数である 2 が出力されます。

なお、サンプルコードでは可変長配列（VLA）を使用していますが、これは標準C++の規格外の機能です。移植性を重視する場合は、vector<bool> の利用を推奨します。