【C++】セットビット数が素数となる数を範囲内で数える方法

この記事では、2つの整数 L と R が与えられたとき、L から R の範囲内にある整数のうち、セットビット(2進表現で1になっているビット)の数が素数であるものの総数を求める方法を解説します。

問題の概要

まず、具体的な例で問題を確認しましょう。

入力: L = 7, R = 12
出力: 6
説明:
7  → 111、セットビット数 = 2(素数)
8  → 1000、セットビット数 = 1(素数ではない)
9  → 1001、セットビット数 = 2(素数)
10 → 1010、セットビット数 = 2(素数)
11 → 1011、セットビット数 = 3(素数)
12 → 1100、セットビット数 = 2(素数)

解決のアプローチ

この問題を解くには、範囲内の各数値を順番に走査し、それぞれのセットビットの総数を調べます。C++では、あらかじめ用意されている関数 __builtin_popcount() を使うことで、セットビットの数を簡単に取得できます。

その後、取得したセットビット数が素数かどうかを判定し、素数であればカウントを1つ増やします。走査が終わった時点でのカウントが答えとなります。

素数判定のポイント

素数判定には、試し割り法を最適化した手法を使用します。2と3で割り切れるかどうかを先に確認し、その後は 6k±1 の形の数だけで割り算を試すことで、計算量を大幅に削減できます。

実装例

#include <iostream>
using namespace std;

bool isPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

void printPrimeSetBits(int l, int r) {
    int tot_bit, count = 0;
    for (int i = l; i <= r; i++) {
        tot_bit = __builtin_popcount(i);
        if (isPrimeNumber(tot_bit))
            count++;
    }
    cout << count;
}

int main() {
    int L = 7, R = 13;
    cout << "" << L << " から " << R << " の間でセットビット数が素数である数の総数 : ";
    printPrimeSetBits(L, R);
    return 0;
}

実行結果

7 から 13 の間でセットビット数が素数である数の総数 : 6

計算量について

このアルゴリズムの時間計算量は O((R − L + 1) × log R) です。各数値のポップカウントはビット長に比例した O(log n) で求められます。一方、セットビット数は32ビット整数でも最大32程度しかないため、素数判定は実質的に定数時間で完了するとみなせます。範囲が広くても効率的に動作する実用的なアプローチです。