C++のビット単位のふるい（Bitwise Sieve）で素数を効率的に求める方法

この記事では、整数 N が与えられたとき、ビット単位のふるい（Bitwise Sieve）を用いて N 未満のすべての素数を効率よく求める方法を解説します。

ビット単位のふるいとは？

ビット単位のふるいは、指定された数より小さいすべての素数を列挙するために用いられる、エラトステネスの篩（Sieve of Eratosthenes）の最適化版です。

通常のエラトステネスの篩では、各数値が素数かどうかを bool 型（1バイト）で管理します。一方、ビット単位のふるいでは整数型の各ビット（1ビット）で素数判定情報を表現します。bool 型は1バイト（8ビット）を消費するため、この手法を採用することでメモリ使用量を約1/8に削減できるのが最大の特徴です。

問題の例

具体例を使って問題を確認しましょう。

• 入力： N = 25
• 出力： 2 3 5 7 11 13 17 19 23

このように、25 未満の素数である 2, 3, 5, 7, 11, 13, 17, 19, 23 が出力できれば成功です。

アルゴリズムのポイント

ビット単位のふるいの処理の流れは、基本的なエラトステネスの篩と同じです。主な工夫点は以下のとおりです。

• 偶数をスキップ： 2 以外の偶数は素数ではないため、奇数のみを対象として管理します。これにより必要なビット数がさらに半分になります。
• ビット操作による管理： 配列のどの要素（prime[x/64]）、どのビット位置（(x>>1)&31）に格納するかをビット演算で計算し、合成数のフラグを立てます。
• 空間計算量の削減： bool 型の配列と比較して、必要なメモリは約1/8で済みます。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <iostream>
#include <math.h>
#include <cstring>
using namespace std;

// x が素数でない（合成数フラグが立っている）かを判定する
bool ifnotPrime(int prime[], int x) {
    return (prime[x/64]&(1<<((x>>1)&31)));
}

// x を合成数としてマークする
bool makeComposite(int prime[], int x) {
    prime[x/64]|=(1<<((x>>1)&31));
}

// ビット単位のふるいによる素数列挙
void bitWiseSieve(int n){
    int prime[n/64];
    memset(prime, 0, sizeof(prime));
    for (int i = 3; i<= sqrt(n); i= i+2) {
        if (!ifnotPrime(prime, i))
            for (int j=pow(i,2), k= i<<1; j<n; j+=k)
                makeComposite(prime, j);
    }
    for (int i = 3; i <= n; i += 2)
        if (!ifnotPrime(prime, i))
            printf("%d\t", i);
}

int main(){
    int N = 37;
    printf("All the prime number less than %d are 2\t", N);
    bitWiseSieve(N);
    return 0;
}

実行結果

All the prime number less than 37 are 2 3 5 7 11 13 17 19 23 29 31 37

このように、37 未満の素数がすべて正しく出力されていることがわかります。

まとめ

ビット単位のふるいは、エラトステネスの篩と同じアルゴリズムをベースにしながら、ビット演算によってメモリ使用量を大幅に削減できる強力な手法です。大きな範囲の素数を扱う競技プログラミングなどで特に有効なので、ぜひ実装方法をマスターしておきましょう。