762. 二进制表示中质数个计算置位

题目链接：762. 二进制表示中质数个计算置位

暴力解法

如果不加思考，这道题完全可以用最直观的暴力破解：直接遍历整个区间，对每一个数字转成二进制后统计 1 的个数，然后用一个函数去检验这个个数到底是不是质数。

from math import sqrt

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        cal = 0
        for k in range(left, right + 1):
            if self.is_prime(k) == 1:
                cal += 1
        return cal

    def is_prime(self, num):
        counter = 0
        bin_num = bin(num)[2:]
        for i in bin_num:
            if i == '1':
                counter += 1
        if counter == 0 or counter == 1:
            return 0
        elif counter == 2:
            return 1
        for j in range(2, int(sqrt(counter)) + 1):
            if counter % j == 0:
                return 0
        return 1

这套解法非常直白，时间复杂度为 $O(n \cdot \sqrt{C})$（其中 $C$ 是二进制字串最大的长度），空间复杂度为 $O(1)$。虽然能跑通，但里面嵌套了寻找 1 的个数和跑拉胯的素数检查循环，运行效率没那么理想，也显得有些啰嗦。

破局思考：数据范围里藏着的优化空间

算法题的优化捷径往往就藏在给定的数据范围里。

我们观察到这道题给出的 $left$ 和 $right$ 的最大范围只有 $10^6$。
稍微转换一下概念：既然数字最多不超过 $10^6$，而 $10^6 < 2^{20}$，也就是说，在这个区间内的任何数字转化成二进制之后，最多也就只有 $20$ 位！

这意味着，里面就算全是 1，它能出现的质数个数也绝对不会多于 20 种。既然可能性这么小，再去手写判断质数的函数、每一次都跑循环去除余数，就显得杀鸡用牛刀了。

所以我们完全可以不用重复劳动——只需预处理出 20 以内的所有质数，通过打表的方式将其转换成一个集合，就能把寻找质数的时间开销硬生生拉到常数时间的 $O(1)$！这就叫作算法里的“空间换时间”。

最优解：极简打表 + 位元运算

不仅如此，我们在计算二进制中 1 的数量时，可以直接调用 Python 底层 C 语言优化过的 int.bit_count() 。
结合 Python 的生成器表达式语法，原本啰里吧嗦的一长串嵌套代码，立刻就能浓缩成了极简的一行流：

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        # 20以内的质数集合，直接打表缓存，获取 O(1) 的查询速度
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        # 极简的生成器表达式，判断每个数的 bit_count 结果是否在表中
        return sum(x.bit_count() in primes for x in range(left, right + 1))

通过观察极小的数据范围直接打表这一技巧，代码不光变得极其精练、美感十足，时间复杂度也直接降至 $O(n)$。有时候换个思路多走一步，往往就能豁然开朗。