0762. Prime Number of Set Bits in Binary Representation

题目信息

题号:

0762

难度:

Easy

主题:

位运算、质数、区间计数

原题:

LeetCode 0762

重点:

对闭区间内每个整数统计二进制表示中的 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 不是质数,因此这个最小单点区间没有符合条件的整数。