#11384. 二进制中1的个数为质数的数目

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

给你两个整数 left 和 right ,统计并输出:在闭区间 [left, right] 范围内,有多少个数的二进制表示中 1 的个数为质数。

例如, 21 的二进制表示为 10101,其中 1 的个数有 3 个,3 是质数。

【提示】

将整数 x 转换为二进制数 b :bitset<30>b(x)

计算二进制数 b 中 1 的个数:b.count()

输入格式

两个整数 left 和 right

输出格式

从 left 到 right中,其二进制表示中 1 的个数为质数的数量

样例

示例 1:

输入:

6 10

输出:

4

解释:
6 -> 110 (有 2 个 1,2 是质数)
7 -> 111 (有 3 个 1,3 是质数)
9 -> 1001 (有 2 个 1,2 是质数)
10-> 1010 (有 2 个 1,2 是质数)
共计 4 个 二进数中 1 的个数为质数的数字。

示例 2:

输入:

10 15

输出:

5

解释:
10 -> 1010 (有 2 个 1, 2 是质数)
11 -> 1011 (有 3 个 1, 3 是质数)
12 -> 1100 (有 2 个 1, 2 是质数)
13 -> 1101 (有 3 个 1, 3 是质数)
14 -> 1110 (有 3 个 1, 3 是质数)
15 -> 1111 (有 4 个 1, 4 不是质数)
共计 5 个 二进数中 1 的个数为质数的数字。

数据范围与提示

1 <= left <= right <= 10^6

0 <= right - left <= 10^4