Pythonで2進表現のセットビット数が素数になる数を数える方法

問題の概要

2つの整数LとRが与えられたとき、範囲[L, R](両端を含む)に含まれる整数の中で、2進表現におけるセットビット(1となっているビット)の個数が素数であるものを数える問題です。

例えば、入力がL = 6、R = 10の場合、出力は4となります。これは、以下の4つの数が条件を満たすためです。

• 6 → 110(セットビット数:2)
• 7 → 111(セットビット数:3)
• 9 → 1001(セットビット数:2)
• 10 → 1010(セットビット数:2)

なお、8は2進表現で1000となり、セットビット数が1(素数ではない)ため対象外です。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. カウンタcountを0で初期化する。
2. LからRまでの各整数jについて、セットビット数を求める。
3. そのセットビット数が[2, 3, 5, 7, 11, 13, 17, 19]のいずれかに含まれていれば、countを1増やす。
4. 最後にcountを返す。

なぜ[2, 3, 5, 7, 11, 13, 17, 19]だけで十分なのか?

一般的な制約ではRは10⁶以下であることが多く、この場合2進表現は最大20桁程度に収まります。つまり、セットビット数は最大でも20未満であり、それ以下の素数である2, 3, 5, 7, 11, 13, 17, 19だけをチェックすれば十分というわけです。

Pythonでの実装例

class Solution:
    def countPrimeSetBits(self, L, R):
        def popcount(i):
            return bin(i)[2:].count('1')
        count = 0
        for j in range(L, R + 1):
            if popcount(j) in [2, 3, 5, 7, 11, 13, 17, 19]:
                count += 1
        return count

ob = Solution()
print(ob.countPrimeSetBits(6, 10))

コードのポイント

• popcount関数:bin(i)[2:]で整数iを「0b」というプレフィックスなしの2進文字列に変換し、count('1')で1の個数を数えています。
• メイン処理:range(L, R + 1)によりLからRまで(両端を含む)を走査し、セットビット数が素数リストに含まれるかどうかを判定しています。

実行結果

入力:

6, 10

出力:

4

計算量について

このアルゴリズムの時間計算量はO((R − L + 1) × log R)です。各数値に対して2進変換とビットカウントを行うため、範囲の幅に比例して処理時間が増加します。範囲が非常に広い場合は、桁DP(桁ごとの動的計画法)などを用いたより効率的なアプローチも検討できます。