0762. Prime Number of Set Bits in Binary Representation¶
题目信息¶
- 题号:
0762
- 难度:
Easy
- 主题:
位运算、质数、区间计数
- 原题:
- 重点:
对闭区间内每个整数统计二进制表示中的 1 的数量;只有该数量本身是质数时才计入答案,数字 1 不是质数
题目重述¶
给定两个整数 left 和 right,统计闭区间 [left, right] 中有多少个整数满足:该整数写成二进制后,值为 1 的位数是一个质数。
二进制中的前导零不计入表示;质数是大于 1 且只有 1 和自身两个正因数的整数,因此 1 不属于质数。
1 <= left <= right <= 10^6,并且 0 <= right - left <= 10^4。
自建示例¶
区间中包含不同的置位数量:
输入:left = 20, right = 25
输出:5
解释:20、21、22、24、25 的二进制表示分别含 2、3、3、2、3 个 1,这些数量都是质数;23 含 4 个 1,不计入答案。
单点区间且置位数量不是质数:
输入:left = 1, right = 1
输出:0
解释:1 的二进制表示是 ``1``,只含一个置位。数字 1 不是质数,因此这个最小单点区间没有符合条件的整数。