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

https://leetcode-cn.com/problems/prime-number-of-set-bits-in-binary-representation/

解法一：

根据提示,数字范围在1~1000000之间,而2^20=1048576>10^6,即20位的二进制可以表示0~1048575之间的任意数,因此不用太花功夫考虑怎么判断质数,只要找出20以内的质数存在集合里,判断是否属于集合即可. 剩下的很简单,对[L, R]的每个数i,每次将i和1进行与操作

class Solution:
    def countPrimeSetBits(self, L: int, R: int) -> int:
        res = 0 
        prime = set([2, 3, 5, 7, 11, 13, 17, 19])    #转成set，查找比list快一些
        set_bit = 0    #计算置位
        for i in range(L, R+1):
            set_bit = 0
            while i > 0:
                set_bit += i & 1
                i >>= 1
            if set_bit in prime:    #查找是否为素数
                res += 1
        return res