### 题目描述 给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。 计算置位位数 就是二进制表示中 1 的个数。 - 例如， 21 的二进制表示 10101 有 3 个计算置位。 ### 输入输出 #### 示例1 ``` 输入：left = 6, right = 10 输出：4 解释： 6 -> 110 (2 个计算置位，2 是质数) 7 -> 111 (3 个计算置位，3 是质数) 9 -> 1001 (2 个计算置位，2 是质数) 10-> 1010 (2 个计算置位，2 是质数) 共计 4 个计算置位为质数的数字。 ``` #### 示例2 ``` 输入：left = 10, right = 15 输出：5 解释： 10 -> 1010 (2 个计算置位, 2 是质数) 11 -> 1011 (3 个计算置位, 3 是质数) 12 -> 1100 (2 个计算置位, 2 是质数) 13 -> 1101 (3 个计算置位, 3 是质数) 14 -> 1110 (3 个计算置位, 3 是质数) 15 -> 1111 (4 个计算置位, 4 不是质数) 共计 5 个计算置位为质数的数字。 ``` **提示：** - 1 <= left <= right <= 10^6 - 0 <= right - left <= 10^4 ### 题目解答 #### 思路 统计从left-right每个数字二进制的数量，然后判断其数量是否为质数。 由于给的数据范围，再10e6范围内，因此最多17位即可表示该数字，因此我们需求的质数也就这么多，可以先求直接保存起来，直接调用即可。 #### 代码实现 ```python class Solution: def isPrime(self, n): if n==1: return False elif n >1 and n <= 3: return True i = 2 while i * i <= n: if n % i == 0: return False i += 1 return True def countPrimeSetBits(self, left: int, right: int) -> int: # 数据范围有限，直接敲出来更快 primes = [False, False, True, True, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False] res = [i for i in range(left, right+1) if primes[i.bit_count()]] return len(res) ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复