Leetcode Day5 1

每日一题ing，感觉可以用到昨天的lowbit就用了，不过真的太慢了。。。

给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。

计算置位位数 就是二进制表示中 1 的个数。

例如， 21 的二进制表示 10101 有 3 个计算置位。

 

class Solution:

    def countPrimeSetBits(self, left: int, right: int) -> int:

        def lowbit(self, x: int) -> int:

            return x & (-x)

        def calculate1(self, n: int) -> int:

            i = 0

            while n:

                n -= lowbit(self, n)

                i += 1

            return i

        def ifzhishu(self, n: int) -> bool:

            if n==1:return False

            for i in range(2, int(pow(n, 0.5))+1):

                if n % i == 0:

                    return False

            return True

        res = 0

        for i in range(left, right+1):

            tmp = calculate1(self, i)

            res1 = ifzhishu(self, tmp)

            if res1 == True: res += 1

        return res

总而言之没有调库，十分暴力……

大佬的话应该是调了个bit_count函数然后打表，十分迅捷了

暴力是不会带来快乐的.jpg